Submission #3456947
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
int read(){
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-1,ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
int n,Len,T;
int x[N],w[N],res[N];
vector <int> v1,v2;
int s1,s2;
bool check(int x){
int L,R;
if (!w[0])
L=(x-1)>>1,R=x>>1;
else
L=x>>1,R=(x-1)>>1;
LL tot=1LL*(L/s1)*Len+v1[L%s1]
+1LL*(R/s2)*Len+v2[R%s2];
//printf("check %d : L = %d , R = %d , tot = %lld\n",x,L,R,tot);
return tot<=(T<<1);
}
int main(){
n=read(),Len=read(),T=read();
v1.clear();
v2.clear();
for (int i=0;i<n;i++){
x[i]=read(),w[i]=read()&1;
if (w[i])
res[i]=(x[i]+T)%Len;
else
res[i]=((x[i]-T)%Len+Len)%Len;
if (!w[i])
v2.push_back(x[i]-x[0]);
else
v1.push_back((x[0]-x[i]+Len)%Len);
}
if (v1.empty()||v2.empty()){
for (int i=0;i<n;i++)
printf("%d\n",res[i]);
return 0;
}
sort(res,res+n);
sort(v1.begin(),v1.end());
//for (auto y : v1)printf("%d ",y);puts("");
//for (auto y : v2)printf("%d ",y);puts("");
s1=v1.size(),s2=v2.size();
int L=1,R=T<<1,ans=0;
while (L<=R){
int mid=(L+R)>>1;
if (check(mid))
L=mid+1,ans=mid;
else
R=mid-1;
}
//printf("%d\n",ans);
int p0;
if (ans==0)
p0=w[0]?(x[0]+T)%Len:(x[0]+Len-T)%Len;
else {
if (!w[0])
L=(ans-1)>>1,R=ans>>1;
else
L=ans>>1,R=(ans-1)>>1;
//printf("L = %d , R = %d\n",L,R);
int tot=L/s1*Len+v1[L%s1]+R/s2*Len+v2[R%s2];
//printf("%d\n",tot);
T=(T<<1)-tot;
LL p=(R/s2*Len+v2[R%s2])-(L/s1*Len+v1[L%s1]);
//printf("T' = %d , p = %lld\n",T,p);
if (w[0]^(ans&1))
p+=T;
else
p-=T;
//printf("pp = %lld\n",p);
p/=2;
p0=((p+x[0])%Len+Len)%Len;
}
//printf("%d\n\n",p0);
int p=lower_bound(res,res+n,p0)-res;
if (w[0]^(ans&1)){
if (n>2&&res[(p+1)%n]==res[p])
p++;
}
else
if (n>2&&res[(p+n-1)%n]==res[p])
p--;
for (int i=0;i<n;i++)
printf("%d\n",res[(p+i)%n]);
return 0;
}
/*
3 10 7
2 1
3 1
7 2
Time
0 2 3 7
1 3 4 6
2 4 5 5
3 4 5 6 1
4 3 6 7
5 2 7 8
6 1 8 9
7 0 9 0 2
*/
Submission Info
Submission Time |
|
Task |
C - Ants on a Circle |
User |
zhouzhendong |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2207 Byte |
Status |
AC |
Exec Time |
27 ms |
Memory |
2892 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
17 ms |
1920 KB |
subtask_1_02.txt |
AC |
13 ms |
1536 KB |
subtask_1_03.txt |
AC |
26 ms |
2892 KB |
subtask_1_04.txt |
AC |
27 ms |
2852 KB |
subtask_1_05.txt |
AC |
4 ms |
640 KB |
subtask_1_06.txt |
AC |
6 ms |
896 KB |
subtask_1_07.txt |
AC |
23 ms |
2684 KB |
subtask_1_08.txt |
AC |
23 ms |
2596 KB |
subtask_1_09.txt |
AC |
15 ms |
1792 KB |
subtask_1_10.txt |
AC |
14 ms |
1664 KB |
subtask_1_11.txt |
AC |
4 ms |
640 KB |
subtask_1_12.txt |
AC |
20 ms |
2552 KB |
subtask_1_13.txt |
AC |
16 ms |
2048 KB |
subtask_1_14.txt |
AC |
14 ms |
1920 KB |
subtask_1_15.txt |
AC |
1 ms |
256 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |