Submission #3819489

---

Source Code Expand

#include <cstdio>
#define ll long long
#define rep(i,j,k) for (i=j;i<=k;i++)
#define down(i,j,k) for (i=j;i>=k;i--)
using namespace std;
const int N=2e5+5,INF=2e9+2;
int n,L,T,i,j,an,bn,ans,x[N],d[N],a[N],b[N],tmp[N],fs[N],ao[N],bo[N],bel[N],p[N],q[N];
ll calc(int t,int a0,int b0,int an,int bn)
{
	int ta=(t+1)/2,tb=t/2;
	ll sum=(ll)ta/an*L+(ll)tb/bn*L;
	ta%=an; tb%=bn;
	if (ta) sum+=a0>0?p[a0+ta-1]-p[a0-1]:p[ta-1];
	if (tb) sum+=q[b0+bn]-q[b0+bn-tb];
	return sum;
}
void solve(int an,int *a,int *ao,int bn,int *b,int *bo)
{
	int l,r,mid,t,i,t0,od;
	rep(i,0,bn-1) tmp[i]=b[i]; rep(i,bn,bn*2-1) tmp[i]=b[i-bn]+L; tmp[bn*2]=INF;
	down(i,bn*2-1,0) if (tmp[i]<=a[0]+L) break; fs[0]=i;
	rep(i,1,an-1) {
		fs[i]=fs[i-1];
		while (tmp[fs[i]+1]<=a[i]+L) fs[i]++;
	}
	rep(i,0,an-1) fs[i]%=bn;
	
	if (an==1) p[0]=L,p[1]=L+L;
	else {
		rep(i,0,an-1) p[i]=(a[(i+1)%an]-a[i]+L)%L;
		rep(i,an,an*2-1) p[i]=p[i-an];
		rep(i,1,an*2-1) p[i]+=p[i-1];
	}
	
	if (bn==1) q[0]=L,q[1]=L+L;
	else {
		rep(i,0,bn-1) q[i]=(b[i]-b[(i+bn-1)%bn]+L)%L;
		rep(i,bn,bn*2-1) q[i]=q[i-bn];
		rep(i,1,bn*2-1) q[i]+=q[i-1];
	}
	
	rep(i,0,an-1)
	{
		t=T;
		t0=(a[i]-b[fs[i]]+L)%L;
		if (t<t0) {
			bel[ao[i]]=ao[i]; continue;
		}
		t-=t0;
		l=0; r=t;
		while (l<r)
		{
			if (r-l>1) mid=(l+r)>>1;
			else mid=r;
			
			if (calc(mid,i,fs[i],an,bn)<=t) l=mid;
			else r=mid-1;
		}
		
		l++;
		if (l%2) {
			od=(l+1)/2;
			bel[ao[i]]=bo[((fs[i]-od+1)%bn+bn)%bn];
		}
		else {
			od=l/2;
			bel[ao[i]]=ao[((i-od)%an+an)%an];
		}
	}
}
int main()
{
//	freopen("ants.in","r",stdin);
//	freopen("ants.out","w",stdout);
	scanf("%d%d%d",&n,&L,&T); T<<=1;
	rep(i,0,n-1) {
		scanf("%d%d",&x[i],&d[i]);
		if (d[i]==1) a[an]=x[i],ao[an]=i,an++;
		else b[bn]=x[i],bo[bn]=i,bn++;
	}
	if (!an || !bn) { rep(i,0,n-1) bel[i]=i; }
	else {
		solve(bn,b,bo,an,a,ao);
		rep(i,0,an-1) a[i]=(L-a[i])%L;
		rep(i,0,bn-1) b[i]=(L-b[i])%L; //symmetric
		solve(an,a,ao,bn,b,bo);
	}
	T>>=1;
	rep(i,0,n-1) {
		if (d[bel[i]]==1) ans=(x[bel[i]]+T)%L;
		else ans=((x[bel[i]]-T)%L+L)%L;
		printf("%d\n",ans);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:75:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&L,&T); T<<=1;
                          ^
./Main.cpp:77:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x[i],&d[i]);
                            ^

Judge Result