Submission #1470110
Source Code Expand
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
char t=getchar();
bool neg=false;
x=0;
for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
if(t=='-')neg=true,t=getchar();
for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
if(x<0)putchar('-'),x=-x;
short a[20]= {},sz=0;
while(x>0)a[sz++]=x%10,x/=10;
if(sz==0)putchar('0');
for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);
int n,l,t,w[100111];
LL x[200111];
LL getrk(LL num)
{
LL ret=0;
for(int i=1;i<=n;i++)//l*t+x[i]<=num
{
LL t;
if(num-x[i]>=0)t=(num-x[i])/l;
else t=-(x[i]-num+l-1)/l;
ret+=t+2000000000+1;
}
return ret;
}
LL getnum(LL rk)
{
LL l=-20000000000000ll,r=20000000000000ll,mid;
while(l<r-1)
{
mid=(l+r)/2;
if(getrk(mid)>=rk)r=mid;
else l=mid;
}
return r;
}
int main()
{
get3(n,l,t);
for(int i=1;i<=n;i++)
{
get2(x[i],w[i]);
if(w[i]==1)x[i]+=t;
else x[i]-=t;
}
if(n==1)
{
printendl((x[1]%l+l)%l);
return 0;
}
//[-2e9*l+x,2e9*l+x]
LL t1=getnum(2000000000ll*n+1),t2=getnum(2000000000ll*n+2);
t1=(t1%l+l)%l;t2=(t2%l+l)%l;
for(int i=1;i<=n;i++)x[i]=(x[i]%l+l)%l;
sort(x+1,x+n+1);for(int i=n+1;i<=n+n;i++)x[i]=x[i-n];
for(int i=1;i<=n;i++)if(x[i]==t1&&x[i+1]==t2)
{
for(int j=0;j<n;j++)printendl(x[i+j]);
break;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Ants on a Circle |
User |
OhWeOnFire |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2100 Byte |
Status |
AC |
Exec Time |
142 ms |
Memory |
3200 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 |
84 ms |
2048 KB |
subtask_1_02.txt |
AC |
68 ms |
1536 KB |
subtask_1_03.txt |
AC |
139 ms |
3200 KB |
subtask_1_04.txt |
AC |
142 ms |
3200 KB |
subtask_1_05.txt |
AC |
22 ms |
640 KB |
subtask_1_06.txt |
AC |
33 ms |
896 KB |
subtask_1_07.txt |
AC |
134 ms |
2816 KB |
subtask_1_08.txt |
AC |
137 ms |
2816 KB |
subtask_1_09.txt |
AC |
89 ms |
1920 KB |
subtask_1_10.txt |
AC |
77 ms |
1664 KB |
subtask_1_11.txt |
AC |
17 ms |
640 KB |
subtask_1_12.txt |
AC |
103 ms |
2816 KB |
subtask_1_13.txt |
AC |
75 ms |
2176 KB |
subtask_1_14.txt |
AC |
69 ms |
2048 KB |
subtask_1_15.txt |
AC |
1 ms |
256 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |