QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#638175 | #9449. New School Term | ucup-team4992 | WA | 65ms | 17232kb | C++20 | 3.0kb | 2024-10-13 15:07:05 | 2024-10-13 15:07:05 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a,i##end=b; i<=i##end; i++)
#define drep(i,a,b) for(int i=a,i##end=b; i>=i##end; i--)
#define repp(i,a,b) for(int i=a,i##end=b; i<i##end; i++)
#define drepp(i,a,b) for(int i=a,i##end=b; i>i##end; i--)
#define Erep(i,x) for(int i=head[x]; i; i=Edge[i].nxt)
#define Srep(i,x) for(int i=x,i##end=x; i; i=(i-1)&i##end)
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define fi first
#define se second
#define PII pair<int,int>
#define coint const int
#define ms(x,a) memset(x,a,sizeof x)
#define CM cerr<<(&S2-&S1)/1024.<<"KB"<<endl
//std::mt19937_64 Rnd {std::chrono::steady_clock::now().time_since_epoch().count()};
// Rnd();
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
using namespace std;
template<class T>inline T lowbit(const T &x) { return x&-x; }
coint N=1e6+5;
int n,m;
int sz[N][2],f[N],dis[N];
ll dp[N];
PII find(int x){
if(x==f[x]) return make_pair(x,0);
PII fx=find(f[x]);
f[x]=fx.fi;
dis[x]^=fx.se;
return make_pair(f[x],dis[x]);
}
void back(int a, int b){
rep(i,1,n){
if(a!=0 && i>=a) dp[i]-=dp[i-a];
if(b!=0 && i>=b) dp[i]-=dp[i-b];
}
}
void insert(int a, int b){
drep(i,n,1){
if(a!=0 && i>=a) dp[i]+=dp[i-a];
if(b!=0 && i>=b) dp[i]+=dp[i-b];
}
}
void solve2(PII fx, PII fy){
back(sz[fx.fi][0],sz[fx.fi][1]);
back(sz[fy.fi][0],sz[fy.fi][1]);
insert(sz[fx.fi][fx.se]+sz[fy.fi][fy.se^1],sz[fx.fi][fx.se^1]+sz[fy.fi][fy.se]);
if(dp[n]){
f[fy.fi]=fx.fi;
dis[fy.fi]=fx.se^fy.se^1;
sz[fx.fi][fx.se]+=sz[fy.fi][fy.se^1];
sz[fx.fi][fx.se^1]+=sz[fy.fi][fy.se];
sz[fy.fi][fy.se]=sz[fy.fi][fy.se^1]=0;
}else{
back(sz[fx.fi][fx.se]+sz[fy.fi][fy.se^1],sz[fx.fi][fx.se^1]+sz[fy.fi][fy.se]);
f[fy.fi]=fx.fi;
dis[fy.fi]=fx.se^fy.se;
sz[fx.fi][fx.se]+=sz[fy.fi][fy.se];
sz[fx.fi][fx.se^1]+=sz[fy.fi][fy.se^1];
sz[fy.fi][fy.se]=sz[fy.fi][fy.se^1]=0;
insert(sz[fx.fi][fx.se]+sz[fy.fi][fy.se],sz[fx.fi][fx.se^1]+sz[fy.fi][fy.se^1]);
}
// rep(i,1,n<<1){
// int x=find(i).fi;
// cout<<"i = "<<i<<" , find("<<i<<") = "<<x<<" , sz = "<<sz[x][0]<<" "<<sz[x][1]<<"\n";
// }
}
bool mark[N];
int ans[N];
int X[N*10],Y[N*10];
void solve(){
dp[0]=1;
cin>>n>>m;
rep(i,1,n<<1) {
f[i]=i;
sz[i][0]=1; sz[i][1]=0;
dis[i]=0;
insert(1,0);
}
rep(i,1,m){
cin>>X[i]>>Y[i];
}
drep(i,m,1){
// cout<<"opt : "<<i<<"\n";
int x=X[i],y=Y[i];
PII fx=find(x),fy=find(y);
if(fx.fi==fy.fi) continue;
solve2(fx,fy);
}
int res=n;
rep(i,1,n<<1){
int x=find(i).fi;
// cout<<"i = "<<i<<" , find("<<i<<") = "<<x<<" , sz = "<<sz[x][0]<<" "<<sz[x][1]<<"\n";
if(mark[x]) continue;
if(res>=sz[x][0] && dp[res-sz[x][0]]) ans[x]=0,res-=sz[x][0];
else ans[x]=1,res-=sz[x][1];
}
rep(i,1,n<<1){
PII x=find(i);
cout<<(ans[x.fi]^x.se);
}
cout<<"\n";
return;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15892kb
input:
2 4 1 3 2 4 1 4 1 2
output:
1010
result:
ok Output is valid. OK
Test #2:
score: 0
Accepted
time: 2ms
memory: 15888kb
input:
3 7 2 5 1 3 4 6 2 6 4 5 2 4 5 6
output:
110010
result:
ok Output is valid. OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 13916kb
input:
1 0
output:
01
result:
ok Output is valid. OK
Test #4:
score: 0
Accepted
time: 2ms
memory: 15892kb
input:
1 1 1 2
output:
10
result:
ok Output is valid. OK
Test #5:
score: 0
Accepted
time: 1ms
memory: 16016kb
input:
2 3 2 4 3 4 1 2
output:
1001
result:
ok Output is valid. OK
Test #6:
score: 0
Accepted
time: 0ms
memory: 15932kb
input:
3 8 4 6 3 5 1 4 2 4 1 6 1 2 3 4 4 5
output:
101010
result:
ok Output is valid. OK
Test #7:
score: 0
Accepted
time: 1ms
memory: 15884kb
input:
4 9 4 7 3 8 1 5 2 7 2 8 6 8 7 8 1 4 1 6
output:
10101001
result:
ok Output is valid. OK
Test #8:
score: 0
Accepted
time: 1ms
memory: 15892kb
input:
5 16 3 6 9 10 2 7 1 10 1 5 2 10 3 5 5 6 3 4 2 5 4 5 3 8 4 7 6 8 1 6 7 10
output:
0010111010
result:
ok Output is valid. OK
Test #9:
score: 0
Accepted
time: 2ms
memory: 15944kb
input:
6 13 4 5 2 9 3 8 4 8 4 11 10 12 3 4 3 9 5 11 2 8 5 10 5 8 1 11
output:
001001110110
result:
ok Output is valid. OK
Test #10:
score: 0
Accepted
time: 0ms
memory: 15944kb
input:
12 153 1 24 16 18 7 14 1 16 20 21 9 14 21 22 4 5 17 24 4 12 5 17 13 24 14 15 12 23 12 16 8 11 14 24 9 16 2 5 6 19 11 17 4 22 4 7 6 16 7 20 8 15 5 24 2 10 10 21 21 24 1 12 11 19 18 21 18 24 12 17 13 22 7 9 13 23 4 9 11 13 15 21 5 7 2 4 15 16 17 19 11 16 11 20 7 8 4 15 13 14 6 18 2 19 9 13 23 24 4 21 ...
output:
111100011001101110000001
result:
ok Output is valid. OK
Test #11:
score: 0
Accepted
time: 2ms
memory: 16156kb
input:
259 33757 472 500 65 336 138 469 307 442 427 458 43 239 17 508 460 466 108 393 79 92 250 483 44 277 17 132 35 57 155 499 184 474 246 272 274 418 457 458 338 372 196 514 31 208 117 187 90 229 153 284 189 355 16 337 146 456 269 271 279 412 305 336 303 441 399 472 85 286 91 97 157 437 137 379 71 360 27...
output:
111000110010111001101110000111000000011111100010101100100010001110101101111110000111000101111100010110101110111100011010101100111010010011101010011010011010011101100111001011110001100111000010101011100110110001001010010010101010010110011001100001010110000100001110101110000010110001010010000110110011...
result:
ok Output is valid. OK
Test #12:
score: 0
Accepted
time: 28ms
memory: 16920kb
input:
811 265557 217 1153 383 1609 165 177 612 1602 1057 1428 37 436 135 1200 368 684 448 722 145 1583 325 1052 246 480 74 148 122 1111 1256 1327 304 1070 1285 1542 802 813 454 1563 265 1193 94 848 432 1156 429 1194 427 1230 1152 1406 1329 1355 702 845 591 1232 877 1288 1257 1549 340 659 1080 1333 910 137...
output:
001000000010111000100000000010100001011010111010110111111110000111010000101011011010001011001010111000001011000011011001000001011010001010000011100001010101100110010101011001101100100000100100001010000000100111110011110010001000000001011101100011100001000000101110100000001001100000011110101100100010...
result:
ok Output is valid. OK
Test #13:
score: -100
Wrong Answer
time: 65ms
memory: 17232kb
input:
1691 323743 1246 2397 1445 2647 2010 2806 2001 2896 802 2258 2679 2976 2203 2875 2445 2698 137 3004 536 1800 2316 2520 594 1517 279 1558 1934 2871 57 1358 357 976 1764 2672 869 2137 1694 2201 491 1906 1177 1414 1304 1377 2454 2653 626 2637 1425 1677 620 876 1326 2085 404 874 626 1565 136 597 2885 31...
output:
111010001000000110110000100100010011101101011001011100101110000011100010001111000001000010100101111010111000111000110011100100110000110001001101110010110111110110110010100101010101000100100010111001011011111110010011000011110101000111011010010110101011011001001110100100110001100101111100111011101010...
result:
wrong answer The number of 0s must be equal to that of 1s.