QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #495000 | #7763. 左蓝右红 | C1942huangjiaxu | 100 ✓ | 603ms | 47668kb | C++14 | 2.7kb | 2024-07-27 18:01:19 | 2024-07-27 18:01:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,P=20051131;
int n,fa[N],rv[N],co[N],tr[N];
struct node{
mutable int l,r,id;
bool operator <(const node a)const{return l<a.l;}
}p[N];
set<node>s;
set<int>S;
void upd(int x,int v){
for(;x<=2*n;x+=x&-x)tr[x]+=v;
}
int sum(int x){
int res=0;
for(;x;x-=x&-x)res+=tr[x];
return res;
}
int ksm(int x,int y){
int res=1;
for(;y;y>>=1,x=1ll*x*x%P)if(y&1)res=1ll*res*x%P;
return res;
}
int gf(int x){
return fa[x]==x?fa[x]:fa[x]=gf(fa[x]);
}
void merge(int x,int y){
fa[gf(x)]=gf(y);
}
void join(int x,int y,bool eq){
if(!x||!y)return;
if(eq)merge(x,y),merge(rv[x],rv[y]);
else merge(x,rv[y]),merge(rv[x],y);
if(gf(x)==gf(rv[x])||gf(y)==gf(rv[y])){
printf("-1\n0\n");
exit(0);
}
}
auto split(int p){
auto it=s.lower_bound({p,0,0});
if(it->l==p)return it;
--it;
int l=it->l,r=it->r,id=it->id;
s.erase(it),s.insert({l,p,id}),s.insert({p,r,id});
return s.lower_bound({p,0,0});
}
auto single(int p){
int o=*S.upper_bound(p);
if(o<=2*n)split(o);
return split(p);
}
auto ins(int p,int id){
S.insert(p);
auto it=single(p);
it->id=id;
upd(p,1);
return it;
}
auto del(int p){
upd(p,-1);
auto it=single(p);
return it;
}
void Add(int l,int r,int id){
int c1=sum(l-1),c2=sum(r);
int il=id,ir=(c2-c1&1)?rv[id]:id,im=(c1&1)?rv[id]:id;
auto itl=ins(l,il),itr=ins(r,ir);
itl=split(l);
for(auto it=next(itl);it!=itr;++it)join(it->id,im,0);
if(c1&1)join(prev(itl)->id,id,1);
int nl=itl->r,nr=itr->l;
if(nl!=nr)s.erase(next(itl),itr);
s.insert({nl,nr,im});
}
void Del(int l,int r){
int c1=sum(l-1),c2=sum(r);
auto itl=del(l),itr=del(r);
itl=split(l);
int il=itl->id,im=(c1&1)?il:rv[il];
for(auto it=next(itl);it!=itr;++it)join(it->id,im,0);
int nl=itl->r,nr=itr->r;
if(itr->l==nl){
node nw=*prev(itl);
nw.r=nr;
s.erase(prev(itl),next(itr));
s.insert(nw);
}else{
node nw=*prev(itl);
nw.r=nl;
s.erase(prev(itl),next(itr));
s.insert(nw);
s.insert({nl,nr,im});
}
S.erase(l),S.erase(r);
}
int main(){
scanf("%d",&n);
for(int i=1,x1,y1,x2,y2;i<=n;++i){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
rv[i]=i+n,rv[i+n]=i;
p[x1]={y1,y2,i},p[x2]={y1,y2,-i};
}
for(int i=1;i<=2*n;++i)fa[i]=i;
S.insert(0),S.insert(2*n+1),S.insert(2*n+2);
s.insert({0,2*n+1,0}),s.insert({2*n+1,2*n+2,0});
for(int i=1;i<=2*n;++i){
if(p[i].id>0)Add(p[i].l,p[i].r,p[i].id);
else Del(p[i].l,p[i].r);
}
for(int i=1;i<=n;++i){
if(!co[gf(i)])co[gf(i)]=1,co[gf(rv[i])]=-1;
if(co[gf(i)]==1)putchar('0');
else putchar('1');
}
putchar(10);
int ct=0;
for(int i=1;i<=2*n;++i)if(fa[i]==i)++ct;
printf("%d\n",ksm(2,ct/2));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 111ms
memory: 14700kb
input:
200000 1 80998 2 135082 3 102065 4 124005 5 329791 6 357016 7 16209 8 249821 9 200857 10 242988 11 310613 12 330241 13 63077 14 212145 15 3305 16 172693 17 80307 18 152165 19 74160 20 277762 21 49627 22 111860 23 14498 24 175254 25 296944 26 307454 27 170816 28 292499 29 251883 30 365222 31 112774 3...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok 2 lines
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 0ms
memory: 7804kb
input:
10 4 3 10 8 13 10 20 16 14 11 16 14 7 17 17 20 3 1 19 15 15 4 18 13 8 2 11 7 2 12 5 18 6 5 12 6 1 9 9 19
output:
-1 0
result:
ok 2 lines
Test #3:
score: 20
Accepted
time: 0ms
memory: 5856kb
input:
9 5 8 6 12 4 5 7 15 16 1 18 2 13 6 14 16 8 17 9 18 11 7 12 11 2 3 3 4 15 9 17 10 1 13 10 14
output:
000000001 128
result:
ok 2 lines
Test #4:
score: 20
Accepted
time: 0ms
memory: 5744kb
input:
13 24 13 25 17 2 5 12 6 7 1 26 25 6 7 10 9 1 8 9 18 20 14 21 19 17 3 22 11 15 4 18 15 4 2 16 22 3 20 14 24 8 16 11 23 5 10 23 12 13 21 19 26
output:
-1 0
result:
ok 2 lines
Test #5:
score: 20
Accepted
time: 0ms
memory: 7996kb
input:
10 15 4 16 5 3 12 19 13 5 1 6 16 12 9 13 19 7 2 18 3 9 14 20 15 10 18 11 20 1 8 2 10 4 6 8 7 14 11 17 17
output:
0011000001 32
result:
ok 2 lines
Test #6:
score: 20
Accepted
time: 0ms
memory: 7844kb
input:
11 9 14 12 19 3 2 21 6 7 1 14 17 11 4 15 9 13 8 17 21 16 15 18 22 8 7 22 20 2 3 6 18 5 10 20 16 4 5 19 13 1 11 10 12
output:
-1 0
result:
ok 2 lines
Test #7:
score: 20
Accepted
time: 0ms
memory: 5940kb
input:
12 9 2 10 12 2 13 6 14 5 10 8 11 20 5 21 9 1 15 14 16 16 1 17 7 12 19 13 20 19 6 22 18 7 21 15 22 18 8 23 17 3 23 4 24 11 3 24 4
output:
000000010001 512
result:
ok 2 lines
Test #8:
score: 20
Accepted
time: 0ms
memory: 7996kb
input:
13 11 3 17 16 8 6 18 7 1 2 3 20 6 9 13 26 10 12 24 15 5 14 7 19 2 1 19 13 12 5 20 22 15 8 21 18 14 4 25 24 16 17 22 21 4 10 26 11 9 23 23 25
output:
-1 0
result:
ok 2 lines
Test #9:
score: 20
Accepted
time: 0ms
memory: 5828kb
input:
9 10 3 13 4 7 7 14 8 12 14 18 15 2 11 9 12 1 17 8 18 11 5 15 6 4 2 5 13 3 1 6 10 16 9 17 16
output:
000000001 64
result:
ok 2 lines
Test #10:
score: 20
Accepted
time: 0ms
memory: 7916kb
input:
10 14 5 16 8 10 12 13 13 6 15 17 19 3 2 11 6 19 4 20 10 2 9 5 16 7 11 18 18 12 7 15 17 1 3 8 14 4 1 9 20
output:
-1 0
result:
ok 2 lines
Test #11:
score: 20
Accepted
time: 0ms
memory: 6012kb
input:
12 5 4 6 10 14 20 22 21 19 2 20 9 7 7 12 8 15 14 18 15 1 16 21 17 3 22 8 23 23 11 24 12 9 18 10 19 4 5 11 6 16 1 17 3 2 13 13 24
output:
000000101101 256
result:
ok 2 lines
Test #12:
score: 20
Accepted
time: 1ms
memory: 5808kb
input:
9 6 5 11 15 1 16 12 18 8 9 9 17 3 12 17 13 10 3 18 11 5 2 7 4 13 8 14 10 4 1 16 14 2 6 15 7
output:
-1 0
result:
ok 2 lines
Test #13:
score: 20
Accepted
time: 1ms
memory: 5940kb
input:
11 14 7 15 10 19 3 20 4 6 16 16 17 1 19 13 20 17 2 18 11 2 5 3 13 8 6 9 18 21 1 22 21 7 9 10 14 4 8 5 15 11 12 12 22
output:
00000010001 128
result:
ok 2 lines
Test #14:
score: 20
Accepted
time: 1ms
memory: 7780kb
input:
11 20 18 21 20 1 13 4 14 7 8 19 10 2 4 16 12 18 1 22 2 13 16 15 19 9 3 10 15 3 6 5 21 8 7 17 22 11 9 14 17 6 5 12 11
output:
-1 0
result:
ok 2 lines
Test #15:
score: 20
Accepted
time: 1ms
memory: 6016kb
input:
10 11 9 12 10 14 3 15 7 19 8 20 14 8 19 9 20 6 12 7 13 1 2 2 11 13 6 16 18 3 16 10 17 4 1 5 15 17 4 18 5
output:
0000001000 512
result:
ok 2 lines
Test #16:
score: 20
Accepted
time: 1ms
memory: 7996kb
input:
10 1 1 14 14 9 2 16 3 2 10 12 11 15 4 20 13 3 7 4 20 7 8 19 16 13 6 18 17 5 5 8 19 6 12 10 15 11 9 17 18
output:
-1 0
result:
ok 2 lines
Test #17:
score: 20
Accepted
time: 1ms
memory: 7992kb
input:
12 17 11 18 24 11 19 12 20 21 16 22 18 16 17 19 21 6 12 20 13 8 9 10 10 23 5 24 6 3 1 4 14 1 4 2 7 13 8 14 15 5 22 7 23 9 2 15 3
output:
000110000000 512
result:
ok 2 lines
Subtask #3:
score: 20
Accepted
Dependency #2:
100%
Accepted
Test #18:
score: 20
Accepted
time: 1ms
memory: 5932kb
input:
8 15 6 16 9 10 1 12 2 3 8 4 10 13 13 14 15 1 11 8 12 9 4 11 5 2 3 5 16 6 7 7 14
output:
00001000 32
result:
ok 2 lines
Test #19:
score: 20
Accepted
time: 1ms
memory: 7860kb
input:
22 34 24 35 35 6 4 7 43 1 39 23 40 3 16 37 17 2 27 26 28 29 23 30 31 14 29 15 41 21 21 38 22 12 5 13 10 11 8 41 9 4 30 5 44 33 6 36 15 19 36 20 42 22 2 27 3 42 1 43 7 39 18 44 19 31 32 32 34 17 12 18 13 24 25 40 26 10 37 25 38 16 11 28 14 8 20 9 33
output:
0011100001000000001100 512
result:
ok 2 lines
Test #20:
score: 20
Accepted
time: 1ms
memory: 7908kb
input:
30 21 13 37 14 14 52 29 53 5 59 7 60 10 3 11 4 6 11 28 12 26 21 44 22 17 35 27 36 16 25 52 26 23 8 41 9 55 31 56 48 1 24 2 38 12 6 13 50 4 16 39 17 3 41 54 42 22 15 57 18 49 57 53 58 38 20 51 23 15 33 43 34 47 43 48 44 19 27 46 28 32 47 33 56 42 51 58 54 59 2 60 30 30 7 31 29 18 32 40 37 8 40 45 45 ...
output:
-1 0
result:
ok 2 lines
Test #21:
score: 20
Accepted
time: 1ms
memory: 5884kb
input:
40 8 9 9 66 11 74 12 75 55 20 57 21 51 11 52 63 70 4 71 19 59 3 60 55 49 12 50 80 3 34 65 35 67 49 68 50 28 1 75 2 34 15 48 16 1 10 2 22 29 23 35 24 46 58 47 76 62 65 63 78 7 14 10 61 23 37 40 38 15 48 16 64 53 69 72 70 58 13 61 26 18 72 21 73 25 28 69 29 13 5 22 6 31 32 32 79 19 46 80 47 43 25 44 3...
output:
-1 0
result:
ok 2 lines
Test #22:
score: 20
Accepted
time: 1ms
memory: 5804kb
input:
53 10 11 98 12 25 54 33 55 23 4 40 5 65 16 66 21 7 44 83 45 3 36 4 88 11 70 39 71 12 47 102 48 56 77 81 78 82 74 97 75 60 1 61 105 91 2 94 3 43 83 44 99 92 25 93 31 104 98 105 102 57 24 58 43 46 72 88 73 16 32 17 90 32 13 45 14 22 66 87 67 51 8 52 63 99 61 100 79 53 28 54 56 19 103 96 104 1 51 2 58 ...
output:
-1 0
result:
ok 2 lines
Test #23:
score: 20
Accepted
time: 1ms
memory: 6036kb
input:
196 102 329 241 330 26 69 27 70 77 230 78 256 135 302 136 311 47 125 174 126 94 385 310 386 73 305 164 306 277 20 278 102 237 28 238 168 207 59 208 244 173 7 319 8 369 37 370 215 203 277 267 278 81 24 82 124 57 353 134 354 263 95 264 355 74 185 192 186 152 33 375 34 161 167 162 207 177 381 248 382 1...
output:
0011000111010101001000100001010000010000001110111001111010000001101001100010010000000111000010111101010010000000111100011010011100101000100010001100000011110100111110100100100110000000011111011011 6955471
result:
ok 2 lines
Test #24:
score: 20
Accepted
time: 0ms
memory: 8012kb
input:
196 153 175 314 176 335 53 336 273 283 10 284 19 103 87 383 88 140 251 200 252 345 195 346 226 285 126 286 181 24 55 75 56 63 383 295 384 61 96 62 235 239 381 244 382 151 79 184 80 7 159 172 160 143 391 217 392 169 94 170 327 77 178 78 197 175 91 176 275 195 183 196 264 281 64 282 333 303 190 304 24...
output:
0110011001000011111101000010100100101001111011100101001100110010010001110111101011000000101000001000101011100010100000011101011011100001110000101001100000010111100000110001111110010100001100000110 524288
result:
ok 2 lines
Test #25:
score: 20
Accepted
time: 0ms
memory: 5864kb
input:
196 161 83 191 84 355 162 356 225 333 91 334 133 239 50 240 98 57 23 189 24 47 40 48 380 33 389 156 390 116 307 218 308 15 134 16 275 93 297 129 298 317 191 318 276 325 107 326 370 371 149 372 375 302 357 379 358 125 159 126 161 85 285 192 286 21 76 22 87 227 33 228 208 6 29 9 30 117 4 118 6 199 129...
output:
0111010010111000110000110011100101101101001111010001111100001011010001001110110100011101100100011111100101001010110000101100100000101010001010010100100001011100100001000000110100111010000101001010 524288
result:
ok 2 lines
Test #26:
score: 20
Accepted
time: 0ms
memory: 8076kb
input:
198 184 163 199 164 137 7 138 366 115 66 116 272 213 349 214 372 82 155 128 156 3 54 4 283 87 85 145 86 225 37 226 235 108 35 227 36 259 333 370 334 35 355 371 356 185 47 186 376 11 21 27 22 349 11 396 12 139 59 140 134 5 95 6 186 195 89 196 298 119 374 120 387 51 30 52 147 179 263 180 383 63 75 327...
output:
011100010001001011110000000101010011100110111101110101010010100001000000010110101000001001111000110001111100011111101101000100111100000010000010101100001111110101001011110101000001010101010000001001 524288
result:
ok 2 lines
Test #27:
score: 20
Accepted
time: 0ms
memory: 5884kb
input:
197 307 29 308 37 19 235 138 236 263 263 331 264 133 327 217 328 66 381 280 382 319 295 320 352 220 99 260 100 169 39 170 84 41 73 346 74 90 63 303 64 264 289 373 290 13 8 14 334 27 87 213 88 327 129 328 320 42 115 172 116 145 7 146 207 135 94 136 390 205 292 206 301 233 61 361 62 203 150 204 341 92...
output:
00000101000101011001011101101100111101010000111011101100011010101000100010001110100111101010111001001001111111110001110010011001011000001010000101000101110001110000100110011011110000100101101000010 4194304
result:
ok 2 lines
Test #28:
score: 20
Accepted
time: 0ms
memory: 7912kb
input:
200 63 43 202 251 3 260 226 347 142 201 361 289 52 36 300 46 140 115 228 238 2 236 276 359 308 154 330 373 8 172 119 187 58 161 355 371 68 213 283 349 82 110 205 296 93 90 193 94 64 169 305 252 208 147 329 382 345 156 395 357 190 327 372 344 321 145 354 395 179 140 340 378 22 286 186 368 70 143 250 ...
output:
-1 0
result:
ok 2 lines
Test #29:
score: 20
Accepted
time: 1ms
memory: 5896kb
input:
197 1 1 198 198 2 2 199 199 3 3 200 200 4 4 201 201 5 5 202 202 6 6 203 203 7 7 204 204 8 8 205 205 9 9 206 206 10 10 207 207 11 11 208 208 12 12 209 209 13 13 210 210 14 14 211 211 15 15 212 212 16 16 213 213 17 17 214 214 18 18 215 215 19 19 216 216 20 20 217 217 21 21 218 218 22 22 219 219 23 23 ...
output:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 2
result:
ok 2 lines
Test #30:
score: 20
Accepted
time: 0ms
memory: 5976kb
input:
197 1 197 394 198 2 196 393 199 3 195 392 200 4 194 391 201 5 193 390 202 6 192 389 203 7 191 388 204 8 190 387 205 9 189 386 206 10 188 385 207 11 187 384 208 12 186 383 209 13 185 382 210 14 184 381 211 15 183 380 212 16 182 379 213 17 181 378 214 18 180 377 215 19 179 376 216 20 178 375 217 21 17...
output:
01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010 2
result:
ok 2 lines
Subtask #4:
score: 25
Accepted
Dependency #3:
100%
Accepted
Test #31:
score: 25
Accepted
time: 1ms
memory: 7868kb
input:
10 7 6 12 7 16 11 18 12 13 3 19 4 3 14 5 15 1 2 11 5 6 17 10 18 4 16 17 19 8 13 9 20 14 1 15 8 2 9 20 10
output:
0000000110 128
result:
ok 2 lines
Test #32:
score: 25
Accepted
time: 1ms
memory: 7896kb
input:
18 1 32 17 33 11 20 33 21 5 2 6 34 19 12 21 13 12 22 18 23 29 3 30 24 27 9 28 10 22 17 23 35 3 8 20 11 15 26 34 27 13 1 14 16 24 19 25 31 4 5 31 6 7 18 8 36 2 7 16 14 35 4 36 15 26 28 32 29 9 25 10 30
output:
001001010011010000 128
result:
ok 2 lines
Test #33:
score: 25
Accepted
time: 1ms
memory: 5880kb
input:
31 26 55 56 56 29 35 50 36 51 4 52 33 21 54 22 60 40 3 41 50 16 61 44 62 8 1 9 34 35 32 36 44 24 23 25 51 48 27 49 43 57 26 58 41 3 17 55 18 32 58 53 59 30 19 31 21 11 2 12 15 14 39 27 40 4 30 38 31 33 22 34 46 13 8 15 9 17 24 60 25 5 48 47 49 61 7 62 20 28 52 43 53 1 5 2 12 20 6 23 16 18 28 19 42 3...
output:
-1 0
result:
ok 2 lines
Test #34:
score: 25
Accepted
time: 1ms
memory: 5976kb
input:
42 8 40 9 46 62 3 77 4 37 15 38 21 57 24 58 67 26 45 27 50 40 19 55 20 13 66 14 70 21 51 83 52 42 9 43 10 12 41 15 82 33 8 34 72 2 48 46 49 29 17 49 18 35 42 36 44 79 26 80 64 24 5 44 6 16 16 17 77 7 14 10 25 64 43 65 81 75 7 76 80 70 83 81 84 50 11 61 12 3 68 53 69 11 59 18 65 66 47 67 71 71 32 72 ...
output:
000000010001100000000011001101110001010110 32768
result:
ok 2 lines
Test #35:
score: 25
Accepted
time: 1ms
memory: 8000kb
input:
52 54 36 55 51 23 77 48 78 24 101 99 102 92 6 93 93 53 8 56 104 21 99 57 100 44 44 62 45 10 80 104 81 15 17 16 26 27 75 32 76 28 74 97 79 47 4 83 5 78 27 79 64 7 2 65 3 13 16 14 25 85 70 86 73 73 10 74 65 11 24 12 85 9 60 88 61 66 11 67 19 6 21 98 22 20 67 36 68 71 38 94 39 40 1 41 12 37 53 38 103 5...
output:
-1 0
result:
ok 2 lines
Test #36:
score: 25
Accepted
time: 5ms
memory: 6056kb
input:
1999 3457 1145 3458 3805 907 29 2798 30 3527 3753 3528 3968 2453 2197 2959 2198 543 2921 2366 2922 3217 2697 3425 2698 320 1471 2051 1472 1055 683 1056 1473 2695 1491 2696 3364 3099 1022 3100 1544 2198 2415 3137 2416 204 2155 1320 2156 3933 244 3934 3063 2923 173 3668 174 87 1710 88 2403 1047 1608 1...
output:
010111100011010000000000011010110011001101101001110000101100110100010100110101000001100011100001001011101010001101111111100100010001111111111010010110001010011111101111100000000110010110110001110011010101111111101110001101001111001110101010000011110110100010111010011001011011101001001110001101010011...
result:
ok 2 lines
Test #37:
score: 25
Accepted
time: 5ms
memory: 5988kb
input:
1998 3015 2485 3016 3721 958 3537 1331 3538 937 438 938 3117 3101 1910 3102 2144 302 3015 3361 3016 971 678 972 3109 3827 2861 3891 2862 95 1872 96 2846 615 2991 2114 2992 2527 2033 2528 2401 1124 3885 3753 3886 1665 2514 1666 3028 418 1053 3495 1054 1943 415 3187 416 3611 58 3612 2210 1596 655 2227...
output:
010010101010110101010011000010000010100011100110000101110000010010111111011010001000100111000110000001010000010101011010100011100000110110011010110111100000001111001010011011001010011101101000000000010100011011001011101100000100111001110111010101001100111100101011101000111101011010001011100011011010...
result:
ok 2 lines
Test #38:
score: 25
Accepted
time: 5ms
memory: 6136kb
input:
1998 3943 98 3944 943 3638 3681 3985 3682 2681 537 3633 538 1048 977 3821 978 437 871 689 872 1032 3359 2991 3360 1277 2935 2405 2936 1611 2387 3295 2388 1615 2789 3533 2790 1805 476 1806 788 3393 1831 3394 2367 588 2009 743 2010 3450 647 3828 648 578 2897 2053 2898 2945 207 3734 208 165 1269 2206 1...
output:
011111111001111101010100000101010010111100110000101110111101000000001000011001000011111111000111001100000000000010111100111001100100010011001111000011111111001001010001001010010110001100110011010100110010010100111111110011111110100010001011111111100101001000101011000110110100011000110001101000010010...
result:
ok 2 lines
Test #39:
score: 25
Accepted
time: 5ms
memory: 8188kb
input:
1999 1847 331 1848 3924 3347 624 3348 1034 513 1167 2081 1168 3233 1584 3234 1748 247 3897 2996 3898 1512 3575 2252 3576 1910 3041 3254 3042 1046 3549 3059 3550 930 1313 1713 1314 2659 64 2660 360 567 3083 2053 3084 1875 865 2828 866 3405 2974 3406 3251 1380 147 2173 148 617 2175 2393 2176 971 1095 ...
output:
001011111011011111011110110011100101100011000001010011001010001011010110110000011100010110010000011110111000110001110110010001000001101000101010111011000110101111100100101100011000110011101010111100011010010001101101001111001100000100010001011010101000101000101100111110111010000001100111100011110101...
result:
ok 2 lines
Test #40:
score: 25
Accepted
time: 5ms
memory: 6000kb
input:
1996 908 1483 3742 1484 1009 1171 1010 3642 897 1770 898 2144 1259 310 1260 1514 2973 488 2974 3184 2681 1335 2812 1336 2136 3161 3563 3162 1032 3631 3528 3632 439 2086 440 2396 157 3619 3974 3620 2109 419 2110 2292 1741 1788 1742 3924 3395 2173 3396 2830 2823 348 2824 672 3533 1207 3534 3302 711 17...
output:
011110001011111011001100110010010000010000111010110101101100111101000100111101010101001111101000000111001010000101000001100101110111110110011010100100110110000011111011101100010100111011110011111001100110000001011011100110000100011100011001111111110110110100011010101100000001111001101000000000100100...
result:
ok 2 lines
Test #41:
score: 25
Accepted
time: 1ms
memory: 7892kb
input:
1999 731 943 1061 2908 2186 1335 3196 3689 1818 933 3662 3139 908 1997 2991 2033 870 1918 3645 3815 1000 3594 3086 3791 1592 1342 1992 2491 1588 65 1857 834 3049 171 3543 3428 1021 1955 3219 2924 2459 408 2936 684 329 2674 1372 3399 2293 160 2301 1424 3015 1826 3530 3192 1803 2103 3763 2819 1828 117...
output:
-1 0
result:
ok 2 lines
Test #42:
score: 25
Accepted
time: 3ms
memory: 6332kb
input:
1998 1 1 1999 1999 2 2 2000 2000 3 3 2001 2001 4 4 2002 2002 5 5 2003 2003 6 6 2004 2004 7 7 2005 2005 8 8 2006 2006 9 9 2007 2007 10 10 2008 2008 11 11 2009 2009 12 12 2010 2010 13 13 2011 2011 14 14 2012 2012 15 15 2013 2013 16 16 2014 2014 17 17 2015 2015 18 18 2016 2016 19 19 2017 2017 20 20 201...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok 2 lines
Test #43:
score: 25
Accepted
time: 3ms
memory: 8260kb
input:
1998 1 1998 3996 1999 2 1997 3995 2000 3 1996 3994 2001 4 1995 3993 2002 5 1994 3992 2003 6 1993 3991 2004 7 1992 3990 2005 8 1991 3989 2006 9 1990 3988 2007 10 1989 3987 2008 11 1988 3986 2009 12 1987 3985 2010 13 1986 3984 2011 14 1985 3983 2012 15 1984 3982 2013 16 1983 3981 2014 17 1982 3980 201...
output:
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
result:
ok 2 lines
Subtask #5:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #4:
100%
Accepted
Test #44:
score: 30
Accepted
time: 1ms
memory: 5940kb
input:
10 15 12 20 13 5 1 6 2 13 7 14 14 8 11 9 15 10 3 11 17 17 6 18 10 7 9 12 16 2 19 16 20 3 8 4 18 1 4 19 5
output:
0000100000 128
result:
ok 2 lines
Test #45:
score: 30
Accepted
time: 1ms
memory: 5824kb
input:
18 20 24 21 31 31 4 32 21 8 7 9 22 3 33 5 34 16 18 17 19 4 32 29 35 24 27 25 28 12 26 26 29 14 9 18 10 1 1 2 8 15 13 28 14 19 5 30 6 10 17 27 20 6 15 11 16 35 11 36 36 22 25 23 30 7 2 13 3 33 12 34 23
output:
000001110000010000 4096
result:
ok 2 lines
Test #46:
score: 30
Accepted
time: 1ms
memory: 5860kb
input:
30 11 44 55 45 15 55 49 56 47 11 48 41 34 29 44 30 52 6 53 15 26 9 27 10 36 2 37 35 38 17 39 54 40 16 41 33 3 59 58 60 25 12 28 31 24 40 29 42 33 25 35 26 1 21 42 22 7 19 8 50 43 4 59 5 2 48 51 49 6 23 14 24 45 38 46 46 56 7 57 47 20 27 21 58 9 34 10 57 12 39 13 51 22 8 23 32 4 13 5 14 31 1 32 3 50 ...
output:
000000111010001000101111001000 8192
result:
ok 2 lines
Test #47:
score: 30
Accepted
time: 1ms
memory: 5932kb
input:
40 10 24 13 25 66 23 74 26 36 18 37 37 67 19 73 20 70 14 71 58 23 33 24 71 12 56 21 57 6 64 72 65 33 43 34 48 78 16 79 44 48 10 62 11 16 21 58 22 35 55 38 78 43 30 44 61 2 69 59 70 19 54 20 59 11 50 55 51 1 45 3 46 46 13 47 15 51 77 52 80 9 8 69 9 77 4 80 5 17 73 45 74 60 29 61 72 4 17 5 34 40 2 41 ...
output:
0000100100110011100010100000001010110000 2048
result:
ok 2 lines
Test #48:
score: 30
Accepted
time: 0ms
memory: 7916kb
input:
53 70 60 77 61 81 56 82 105 31 19 45 20 12 103 17 104 98 39 99 98 80 8 83 106 2 47 101 48 44 41 52 42 88 66 89 97 59 57 60 58 53 77 54 78 94 49 95 88 48 63 103 64 1 54 32 55 6 33 24 34 37 3 76 4 21 101 57 102 42 32 43 62 22 15 78 16 72 23 87 24 15 27 92 28 40 72 51 73 79 5 84 45 9 71 49 74 14 92 105...
output:
-1 0
result:
ok 2 lines
Test #49:
score: 30
Accepted
time: 590ms
memory: 19468kb
input:
199996 304183 95897 387849 95898 141930 329185 389861 329186 227971 15864 227972 90890 263303 158007 263304 162684 198405 281434 198406 281767 77218 33261 209110 33262 347253 10038 347254 256395 33325 264833 373169 264834 133579 283525 133580 383844 114423 164440 114424 309832 162235 386873 295607 3...
output:
001110101101110101100001011111010011000001000110000111111100111101001101001101110111000100000101010011110101110110000010101010110100110000100100011111000110110000100011100010110100101000100111100001101101010111100110010011100001101111000000010111011100001010100100110101110011010010000001010110111011...
result:
ok 2 lines
Test #50:
score: 30
Accepted
time: 589ms
memory: 19388kb
input:
199996 154154 105149 368078 105150 30047 364579 124023 364580 351389 23600 351390 385571 14433 11373 100273 11374 20012 212719 60463 212720 45815 314555 164710 314556 158202 19999 343384 20000 233163 31089 258592 31090 149141 273477 149142 337146 221300 108209 344316 108210 368610 192021 395609 1920...
output:
001000001001111111000111100111111111111101011000111000101101101000101100101000000001011100010001011000111110000100000110001001100010000101011010010001001101101001100000111100001000110101101011000011111011010111011111111100000010101101000011111000011010110010001010011011111000000100111001100010000111...
result:
ok 2 lines
Test #51:
score: 30
Accepted
time: 603ms
memory: 19024kb
input:
199998 30878 122257 47554 122258 90172 244559 125367 244560 292935 215197 298326 215198 120207 30359 130705 30360 75108 112273 94706 112274 187307 12755 270843 12756 65219 323781 90490 323782 91753 29703 281259 29704 25411 241708 25412 288292 70029 163968 70030 339468 253943 248987 397229 248988 514...
output:
000000001101110100110110110101110101010011011001011010100001000101110111111100100111000011110100010010001000110000101101111010010101011001101100111010111011000101110001000101110011010000111001000000111111101111101000000001001000000011000010001010000110101101100111101100100101010110111010011001100000...
result:
ok 2 lines
Test #52:
score: 30
Accepted
time: 48ms
memory: 14824kb
input:
200000 68614 29045 393800 345837 86227 139850 172182 251847 127788 47226 377431 237859 245208 102631 261510 174110 177274 83186 393409 306425 111045 126466 158700 273245 8901 49268 276689 240171 67005 89123 186528 130497 64682 82340 374944 221402 141920 124319 275975 301242 177146 375663 329121 3870...
output:
-1 0
result:
ok 2 lines
Test #53:
score: 30
Accepted
time: 598ms
memory: 47668kb
input:
199999 1 1 200000 200000 2 2 200001 200001 3 3 200002 200002 4 4 200003 200003 5 5 200004 200004 6 6 200005 200005 7 7 200006 200006 8 8 200007 200007 9 9 200008 200008 10 10 200009 200009 11 11 200010 200010 12 12 200011 200011 13 13 200012 200012 14 14 200013 200013 15 15 200014 200014 16 16 20001...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok 2 lines
Test #54:
score: 30
Accepted
time: 310ms
memory: 35900kb
input:
199996 1 199996 399992 199997 2 199995 399991 199998 3 199994 399990 199999 4 199993 399989 200000 5 199992 399988 200001 6 199991 399987 200002 7 199990 399986 200003 8 199989 399985 200004 9 199988 399984 200005 10 199987 399983 200006 11 199986 399982 200007 12 199985 399981 200008 13 199984 3999...
output:
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
result:
ok 2 lines