QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638175#9449. New School Termucup-team4992WA 65ms17232kbC++203.0kb2024-10-13 15:07:052024-10-13 15:07:05

Judging History

你现在查看的是最新测评结果

  • [2024-10-13 15:07:05]
  • 评测
  • 测评结果:WA
  • 用时:65ms
  • 内存:17232kb
  • [2024-10-13 15:07:05]
  • 提交

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.