QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524581#8748. 简单博弈ucup-team052AC ✓754ms103336kbC++235.6kb2024-08-19 20:16:342024-08-19 20:16:36

Judging History

This is the latest submission verdict.

  • [2024-08-19 20:16:36]
  • Judged
  • Verdict: AC
  • Time: 754ms
  • Memory: 103336kb
  • [2024-08-19 20:16:34]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const int N=505;


int f[N][N][100];
int tr[512];
int vis1[N],vis2[N];
int mex(vector<int> f)
{
	if(f.empty()) return 0;
	sort(f.begin(),f.end());
	int cur=0;
	for(int i=0;;i++)
	{
		while(cur+1<(int)f.size()&&f[cur]<i) cur++;
		if(f[cur]!=i) return i;
	}
	assert(0);
}
int p[5],q[5];
int get(vector<pair<int,int>> a)
{
	int hsh=0;
	for(int i=0;i<(int)a.size();i++)
	{
		int p=a[i].first,q=a[i].second;
		hsh|=1<<((p-1)*3+q-1);
	}
	return hsh;
}
int gethsh(vector<pair<int,int>> a)
{
	return tr[get(a)];
}
int work()
{
	int n,m; scanf("%d %d",&n,&m);
	vector<pair<int,int>> a(3);
	for(int i=0;i<3;i++) scanf("%d %d",&a[i].first,&a[i].second);
	memset(vis1,0,sizeof(vis1));
	memset(vis2,0,sizeof(vis2));
	int c1=0,c2=0;
	for(int i=0;i<3;i++)
	{
		if(!vis1[a[i].first]) vis1[a[i].first]=++c1;
		if(!vis2[a[i].second]) vis2[a[i].second]=++c2;
		a[i].first=vis1[a[i].first];
		a[i].second=vis2[a[i].second];
	}
	assert(f[n][m][gethsh(a)]!=-1);
	return f[n][m][gethsh(a)];
}
int vis[512];
void init(vector<int> ned)
{
	// cout<<ned.size()<<endl;
	int lim=500;
	for(int n=1;n<=lim;n++) for(int m=1;m<=lim;m++)
	{
		for(int st:ned)
		{
			vector<pair<int,int>> a;
			for(int j=0;j<9;j++) if(st>>j&1) a.emplace_back(j/3+1,j%3+1);
			int tn=0,tm=0;
			for(int i=0;i<(int)a.size();i++) tn=max(tn,a[i].first),tm=max(tm,a[i].second);
			if(tn>n||tm>m) continue;
			tn++,tm++;
			tn=min(tn,n),tm=min(tm,m);
			vector<int> sg;
			{
				for(int i=1;i<=tn;i++)
				{
					int tmp=0;
					int cnt=0;
					for(int j=0;j<(int)a.size();j++)
					{
						int p=a[j].first,q=a[j].second;
						if(p!=i)
						{
							tmp|=1<<((p-(p>i)-1)*3+q-1);
						}
						else cnt++;
					}
					int nw=tr[tmp];
					if(cnt!=m) sg.push_back(f[n-1][m][nw]);
				}
			}
			{
				for(int i=1;i<=tm;i++)
				{
					int tmp=0,cnt=0;
					for(int j=0;j<(int)a.size();j++)
					{
						int p=a[j].first,q=a[j].second;
						if(q!=i)
						{
							tmp|=1<<((p-1)*3+q-(q>i)-1);
						}
						else cnt++;
					}
					int nw=tr[tmp];
					if(cnt!=n) sg.push_back(f[n][m-1][nw]);
				}
			}
			{
				for(int i=1;i<=tn;i++) for(int j=1;j<=tm;j++)
				{
					int tmp=0,cnt=0;
					for(int k=0;k<(int)a.size();k++)
					{
						int p=a[k].first,q=a[k].second;
						if(p!=i&&q!=j)
						{
							tmp|=1<<((p-(p>i)-1)*3+q-(q>j)-1);
						}
						else cnt++;
					}
					int nw=tr[tmp];
					if(cnt!=n+m-1) sg.push_back(f[n-1][m-1][nw]);
				}
			}
			f[n][m][st]=mex(sg);
		}
	}
	// for(int i=1;i<=lim;i++) for(int j=1;j<=lim;j++) for(int st:ned) printf("%d %d %d : %d\n",i,j,st,f[i][j][st]);
}
int main() {
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	for(int i=0;i<512;i++)
	{
		if(__builtin_popcount(i)>3) continue;
		vector<pair<int,int>> f;
		for(int j=0;j<9;j++) if(i>>j&1) f.emplace_back(j/3+1,j%3+1);
		for(int c=1;c<=3;c++) p[c]=c,q[c]=c;
		int mn=123456;
		do{
			for(int d=1;d<=3;d++) q[d]=d;
			do{
				vector<pair<int,int>> nw;
				for(int j=0;j<(int)f.size();j++) nw.emplace_back(p[f[j].first],q[f[j].second]);
				mn=min(mn,get(nw));
			}while(next_permutation(q+1,q+4));
		}while(next_permutation(p+1,p+4));
		tr[get(f)]=mn;
		vis[mn]=1;
//		printf("%d : %d\n",i,mn);
	}
	vector<int> ned;
	for(int i=0;i<512;i++) if(vis[i]) ned.push_back(i);
	init(ned);
//	cout<<mx<<endl;
//	cout<<sizeof(f)/1024.0/1024<<endl;
	int T; cin>>T;
	int ans=0;
	while(T--)
	{
		ans^=work();
//		cout<<T<<endl;
	}
	if(ans) printf("OvO\n");
	else printf("QAQ\n");
	return 0;
}

/*
1 1 0 : 0
1 1 1 : 0
1 1 3 : -1
1 1 7 : -1
1 1 9 : -1
1 1 10 : -1
1 1 11 : -1
1 1 14 : -1
1 1 73 : -1
1 1 74 : -1
1 1 84 : -1
1 2 0 : 1
1 2 1 : 1
1 2 3 : 1
1 2 7 : -1
1 2 9 : -1
1 2 10 : -1
1 2 11 : -1
1 2 14 : -1
1 2 73 : -1
1 2 74 : -1
1 2 84 : -1
1 3 0 : 0
1 3 1 : 0
1 3 3 : 0
1 3 7 : 0
1 3 9 : -1
1 3 10 : -1
1 3 11 : -1
1 3 14 : -1
1 3 73 : -1
1 3 74 : -1
1 3 84 : -1
1 4 0 : 1
1 4 1 : 1
1 4 3 : 1
1 4 7 : 1
1 4 9 : -1
1 4 10 : -1
1 4 11 : -1
1 4 14 : -1
1 4 73 : -1
1 4 74 : -1
1 4 84 : -1
2 1 0 : 1
2 1 1 : 1
2 1 3 : -1
2 1 7 : -1
2 1 9 : 1
2 1 10 : -1
2 1 11 : -1
2 1 14 : -1
2 1 73 : -1
2 1 74 : -1
2 1 84 : -1
2 2 0 : 2
2 2 1 : 2
2 2 3 : 2
2 2 7 : -1
2 2 9 : 2
2 2 10 : 2
2 2 11 : 2
2 2 14 : -1
2 2 73 : -1
2 2 74 : -1
2 2 84 : -1
2 3 0 : 3
2 3 1 : 3
2 3 3 : 3
2 3 7 : 3
2 3 9 : 3
2 3 10 : 3
2 3 11 : 3
2 3 14 : 3
2 3 73 : -1
2 3 74 : -1
2 3 84 : -1
2 4 0 : 2
2 4 1 : 2
2 4 3 : 2
2 4 7 : 2
2 4 9 : 2
2 4 10 : 2
2 4 11 : 2
2 4 14 : 2
2 4 73 : -1
2 4 74 : -1
2 4 84 : -1
3 1 0 : 0
3 1 1 : 0
3 1 3 : -1
3 1 7 : -1
3 1 9 : 0
3 1 10 : -1
3 1 11 : -1
3 1 14 : -1
3 1 73 : 0
3 1 74 : -1
3 1 84 : -1
3 2 0 : 3
3 2 1 : 3
3 2 3 : 3
3 2 7 : -1
3 2 9 : 3
3 2 10 : 3
3 2 11 : 3
3 2 14 : -1
3 2 73 : 3
3 2 74 : 3
3 2 84 : -1
3 3 0 : 0
3 3 1 : 0
3 3 3 : 0
3 3 7 : 0
3 3 9 : 0
3 3 10 : 0
3 3 11 : 0
3 3 14 : 0
3 3 73 : 0
3 3 74 : 0
3 3 84 : 0
3 4 0 : 1
3 4 1 : 1
3 4 3 : 1
3 4 7 : 1
3 4 9 : 1
3 4 10 : 1
3 4 11 : 1
3 4 14 : 1
3 4 73 : 1
3 4 74 : 1
3 4 84 : 1
4 1 0 : 1
4 1 1 : 1
4 1 3 : -1
4 1 7 : -1
4 1 9 : 1
4 1 10 : -1
4 1 11 : -1
4 1 14 : -1
4 1 73 : 1
4 1 74 : -1
4 1 84 : -1
4 2 0 : 2
4 2 1 : 2
4 2 3 : 2
4 2 7 : -1
4 2 9 : 2
4 2 10 : 2
4 2 11 : 2
4 2 14 : -1
4 2 73 : 2
4 2 74 : 2
4 2 84 : -1
4 3 0 : 1
4 3 1 : 1
4 3 3 : 1
4 3 7 : 1
4 3 9 : 1
4 3 10 : 1
4 3 11 : 1
4 3 14 : 1
4 3 73 : 1
4 3 74 : 1
4 3 84 : 1
4 4 0 : 2
4 4 1 : 2
4 4 3 : 2
4 4 7 : 2
4 4 9 : 2
4 4 10 : 2
4 4 11 : 2
4 4 14 : 2
4 4 73 : 2
4 4 74 : 2
4 4 84 : 2
OvO
*/

詳細信息

Test #1:

score: 100
Accepted
time: 725ms
memory: 102768kb

input:

100000
215 4
6 1
59 1
71 4
1 482
1 311
1 381
1 26
3 428
3 81
2 359
1 310
222 220
108 40
16 2
11 79
4 223
4 73
4 103
3 51
214 442
174 261
186 418
202 379
146 464
61 193
85 102
117 206
3 1
3 1
2 1
1 1
357 356
199 222
97 15
257 15
30 2
28 2
4 1
12 2
308 308
32 110
56 157
234 171
347 346
243 89
166 140
...

output:

OvO

result:

ok single line: 'OvO'

Test #2:

score: 0
Accepted
time: 725ms
memory: 102640kb

input:

100000
494 303
141 173
343 269
451 163
4 370
4 46
1 100
3 135
226 3
21 3
116 1
47 3
77 52
65 27
19 4
69 50
205 235
164 101
106 183
27 16
4 2
3 2
1 2
4 2
364 364
54 50
155 83
21 181
432 434
295 302
332 91
258 264
324 326
136 171
239 155
300 81
1 4
1 3
1 2
1 4
177 435
20 326
170 256
175 179
1 4
1 3
1 ...

output:

QAQ

result:

ok single line: 'QAQ'

Test #3:

score: 0
Accepted
time: 689ms
memory: 102636kb

input:

100000
91 476
28 345
28 379
20 119
4 3
4 1
1 2
4 3
117 77
33 74
92 38
102 26
2 3
2 2
1 1
1 3
443 3
252 1
305 3
106 1
410 3
156 3
380 3
135 2
222 275
135 223
181 134
53 241
106 105
100 32
92 27
44 88
140 267
112 129
129 194
133 234
3 489
2 2
3 267
2 9
1 410
1 348
1 315
1 119
101 102
71 73
44 61
56 55...

output:

OvO

result:

ok single line: 'OvO'

Test #4:

score: 0
Accepted
time: 725ms
memory: 102312kb

input:

100000
1 256
1 254
1 90
1 39
4 373
2 6
4 365
3 265
229 2
67 2
2 1
100 2
130 129
102 57
22 82
20 29
1 4
1 1
1 2
1 3
3 2
1 1
2 2
1 2
415 384
109 278
281 175
285 182
2 455
1 196
1 221
1 335
108 385
82 145
108 143
34 57
369 260
361 226
365 124
369 182
3 2
1 1
3 2
1 2
13 3
12 3
3 3
2 1
4 2
3 2
3 1
2 2
40...

output:

QAQ

result:

ok single line: 'QAQ'

Test #5:

score: 0
Accepted
time: 702ms
memory: 102640kb

input:

100000
446 178
5 66
276 167
380 142
4 156
1 148
1 2
4 94
58 309
8 288
19 215
51 258
3 4
1 2
3 3
2 1
297 4
221 2
290 2
65 3
130 4
20 3
40 1
56 1
226 383
105 140
178 189
209 5
4 1
3 1
4 1
2 1
182 493
12 215
56 189
50 34
102 1
95 1
89 1
48 1
305 145
237 61
6 55
300 117
383 468
175 318
359 112
204 196
3...

output:

OvO

result:

ok single line: 'OvO'

Test #6:

score: 0
Accepted
time: 754ms
memory: 103336kb

input:

100000
281 285
167 24
190 98
212 189
310 1
134 1
140 1
123 1
92 90
50 28
23 52
42 41
171 1
54 1
114 1
10 1
3 1
1 1
2 1
3 1
483 272
114 80
284 209
399 180
4 4
3 4
3 1
1 3
240 19
117 14
166 13
231 11
445 55
172 24
238 2
249 3
283 2
217 1
74 2
87 2
314 343
231 322
302 226
310 68
260 323
231 82
233 193
...

output:

QAQ

result:

ok single line: 'QAQ'

Test #7:

score: 0
Accepted
time: 710ms
memory: 102784kb

input:

100000
2 433
1 289
2 338
2 143
19 18
14 17
12 12
2 6
4 125
1 78
1 105
1 10
397 21
76 21
62 1
71 11
1 4
1 3
1 2
1 4
4 4
3 4
2 3
4 1
3 2
2 1
1 1
1 2
76 79
25 49
55 62
68 29
455 455
40 19
170 5
245 187
18 390
16 41
18 178
18 241
4 2
1 1
1 2
3 1
3 473
1 41
2 127
1 196
351 3
112 3
201 3
149 2
3 258
3 210...

output:

OvO

result:

ok single line: 'OvO'

Test #8:

score: 0
Accepted
time: 723ms
memory: 103048kb

input:

100000
235 235
86 155
200 12
84 226
349 462
284 345
342 81
344 386
336 170
249 47
283 136
295 20
318 158
5 28
189 19
111 77
124 486
59 227
90 161
106 184
447 207
446 103
136 77
5 85
209 210
158 105
34 160
80 146
103 355
91 187
95 207
99 137
221 3
194 1
147 1
68 3
204 50
36 13
197 12
202 8
3 2
3 2
3 ...

output:

QAQ

result:

ok single line: 'QAQ'

Test #9:

score: 0
Accepted
time: 720ms
memory: 102660kb

input:

100000
16 241
14 137
8 33
5 97
351 301
23 121
143 19
329 20
2 4
2 1
2 2
1 2
325 182
160 152
297 106
241 98
3 255
3 200
1 131
3 93
3 2
2 1
1 1
3 2
4 1
1 1
4 1
3 1
311 88
152 32
157 81
251 13
232 234
92 35
229 64
32 17
1 3
1 3
1 1
1 2
338 467
33 142
31 435
194 166
161 425
154 150
2 374
74 112
132 132
...

output:

OvO

result:

ok single line: 'OvO'

Test #10:

score: 0
Accepted
time: 726ms
memory: 102440kb

input:

100000
3 2
3 2
2 2
2 1
276 4
46 2
152 2
60 2
3 2
3 1
1 2
3 2
106 105
13 62
71 14
71 57
182 369
86 110
92 205
45 60
305 4
305 1
22 2
290 2
2 296
1 47
1 292
1 285
72 1
35 1
52 1
43 1
321 4
166 3
319 4
112 1
1 82
1 82
1 41
1 49
129 206
34 107
91 78
97 183
2 2
2 2
1 1
2 1
319 402
179 128
251 194
302 202...

output:

QAQ

result:

ok single line: 'QAQ'

Test #11:

score: 0
Accepted
time: 722ms
memory: 102640kb

input:

100000
288 287
230 175
194 262
41 63
319 465
5 393
213 412
305 317
2 327
2 113
2 149
1 69
309 421
207 364
220 56
293 392
160 20
109 9
152 9
154 11
64 66
38 14
21 26
29 42
336 393
7 287
154 343
317 222
231 4
94 1
177 2
53 3
2 4
1 1
2 2
1 4
237 235
115 151
57 88
64 47
3 432
2 44
2 398
2 404
59 29
1 9
...

output:

OvO

result:

ok single line: 'OvO'

Test #12:

score: 0
Accepted
time: 721ms
memory: 102356kb

input:

100000
269 123
178 66
117 84
17 9
3 40
3 25
2 32
3 15
2 140
2 45
1 66
2 59
243 178
66 58
45 77
110 91
147 1
56 1
48 1
137 1
72 165
29 99
67 145
10 5
2 2
1 1
1 2
2 1
4 91
2 9
1 81
2 23
484 2
417 1
416 2
55 2
70 69
63 40
65 56
57 22
83 202
16 27
22 139
43 102
196 2
43 1
23 2
31 1
467 8
447 4
21 5
266 ...

output:

QAQ

result:

ok single line: 'QAQ'

Test #13:

score: 0
Accepted
time: 724ms
memory: 102288kb

input:

100000
3 209
3 95
1 27
3 125
264 450
260 265
263 169
264 371
3 106
1 41
2 98
3 8
2 500
2 76
2 336
2 145
1 193
1 54
1 187
1 2
2 4
2 1
1 4
1 1
171 415
54 87
67 66
163 340
4 3
2 2
2 3
2 1
39 72
14 11
11 25
39 55
1 3
1 2
1 3
1 1
7 1
5 1
1 1
4 1
165 1
101 1
157 1
9 1
245 2
210 1
163 2
40 1
380 497
259 31...

output:

OvO

result:

ok single line: 'OvO'

Test #14:

score: 0
Accepted
time: 723ms
memory: 103152kb

input:

100000
72 496
72 285
72 401
72 477
1 31
1 15
1 13
1 1
349 4
331 4
219 2
38 3
2 4
2 2
2 3
1 2
123 123
48 63
115 34
71 72
351 303
114 52
302 180
339 146
449 480
439 176
447 443
449 338
2 284
1 111
2 248
2 103
184 355
159 50
169 206
180 282
3 292
1 199
3 97
2 266
117 4
38 4
24 3
50 3
31 3
5 2
9 1
10 2
...

output:

QAQ

result:

ok single line: 'QAQ'

Test #15:

score: 0
Accepted
time: 723ms
memory: 102792kb

input:

100000
315 3
107 3
306 2
171 2
2 2
2 1
2 2
1 2
1 373
1 234
1 178
1 360
4 38
3 9
3 8
3 1
12 485
8 87
8 474
10 479
3 263
2 231
2 34
3 253
2 446
1 195
2 102
1 408
92 285
27 79
30 125
92 17
55 4
26 1
34 4
40 2
3 286
2 20
1 163
2 132
67 295
63 101
64 265
65 104
316 318
82 5
37 304
258 223
2 197
1 38
2 46...

output:

OvO

result:

ok single line: 'OvO'

Test #16:

score: 0
Accepted
time: 697ms
memory: 102416kb

input:

100000
378 4
124 4
239 3
14 2
54 52
15 2
50 21
23 8
275 275
36 186
272 191
180 175
217 309
164 6
173 301
200 189
69 1
23 1
65 1
32 1
4 3
1 2
3 2
3 1
271 271
252 3
54 16
124 5
184 2
162 1
56 1
74 1
94 3
50 2
33 1
16 1
176 4
11 4
12 1
7 3
358 414
2 320
40 129
317 289
102 333
30 209
38 200
46 219
290 2...

output:

QAQ

result:

ok single line: 'QAQ'

Test #17:

score: 0
Accepted
time: 674ms
memory: 102444kb

input:

100000
1 3
1 2
1 1
1 3
15 17
12 17
6 9
2 7
474 473
240 285
451 273
248 51
414 1
178 1
10 1
167 1
100 2
1 2
56 2
28 1
2 343
2 276
1 136
2 98
2 332
2 148
1 80
1 45
1 4
1 4
1 2
1 1
280 4
13 1
50 2
260 2
254 29
78 27
209 3
10 24
261 3
219 2
64 2
21 1
4 4
3 2
2 1
2 4
3 3
2 3
1 2
1 1
138 387
69 337
11 223...

output:

OvO

result:

ok single line: 'OvO'

Test #18:

score: 0
Accepted
time: 713ms
memory: 102568kb

input:

100000
3 129
1 63
3 118
3 18
39 2
34 2
36 2
23 2
1 192
1 15
1 161
1 97
64 62
62 60
62 13
61 2
408 2
150 2
260 2
210 2
395 393
299 87
388 208
76 256
3 4
2 4
1 1
1 4
1 432
1 33
1 72
1 119
4 1
4 1
1 1
2 1
294 3
24 3
133 1
222 2
135 441
16 180
96 121
98 121
269 146
228 94
60 103
147 146
468 3
332 1
419 ...

output:

QAQ

result:

ok single line: 'QAQ'

Test #19:

score: 0
Accepted
time: 732ms
memory: 102440kb

input:

100000
398 397
216 140
299 394
152 336
3 498
3 248
3 276
3 23
35 398
7 173
34 370
9 121
450 496
214 182
221 336
400 234
427 2
192 1
287 1
271 1
483 296
257 29
422 44
474 233
3 1
3 1
2 1
1 1
355 355
21 18
237 195
134 330
380 458
35 18
1 17
159 443
2 120
1 12
2 73
1 20
79 311
33 308
52 201
73 58
3 1
2...

output:

OvO

result:

ok single line: 'OvO'

Test #20:

score: 0
Accepted
time: 703ms
memory: 102440kb

input:

100000
472 470
21 286
207 110
374 189
4 88
1 72
2 35
2 58
186 338
95 164
186 5
186 168
132 489
33 1
77 256
87 3
4 2
1 2
4 2
3 2
455 301
208 125
207 93
386 250
319 31
170 30
78 11
149 18
4 4
3 3
1 2
3 4
2 479
2 204
1 61
1 150
3 1
3 1
1 1
2 1
4 271
2 137
4 111
3 117
2 3
1 3
1 1
2 3
362 473
324 234
328...

output:

QAQ

result:

ok single line: 'QAQ'