QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102704#6305. Chinese CheckerkingsnowWA 27ms3596kbC++144.4kb2023-05-03 16:20:512023-05-03 16:21:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 16:21:07]
  • 评测
  • 测评结果：WA
  • 用时：27ms
  • 内存：3596kb
查看
  • [2023-05-03 16:20:51]
  • 提交

answer

//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define getchar nc
#define sight(c) ('0'<=c&&c<='9')
#define swap(a,b) a^=b,b^=a,a^=b
#define LL long long
#define debug(a) cout<<#a<<" is "<<a<<"\n"
#define dput(a) puts("a")
#define eho(x) for(int i=head[x];i;i=net[i])
#define fi first
#define se second
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class T>
inline void read(T &x){// unsigned
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
template <class T> void write(T x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
template <class T> inline void writeln(T x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }
template <class T> inline void writel(T x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
using namespace std;
#define pii pair<int,int>
map<pii,int> ma,usd;
int L[19]={0,1,1,1,1,-3,-2,-1,0,1,1,1,1,1,6,7,8,9};
int R[19]={0,1,2,3,4,9,9,9,9,9,10,11,12,13,9,9,9,9};
bool ok(pii Z){
	if (ma.count(Z)) return 0;
	if (Z.fi<1||Z.fi>17) return 0;
	if (L[Z.fi]>Z.se||R[Z.fi]<Z.se) return 0;
	return 1;
} 

#define N 182
int T,n,a[N],b[N];
queue<pii> Q;
signed main() {
	#ifdef LOCAL
	//	freopen("test.in", "r", stdin);
	//	freopen("test.out", "w", stdout);
	#endif
	scanf("%d",&T);
	while (T--) {
		scanf("%d",&n);
		for (int i=1;i<=n;i++) {
			scanf("%d%d",&a[i],&b[i]);
			if (5<=a[i]&&a[i]<=8) b[i]-=9-a[i];
			if (a[i]>=14) b[i]+=a[i]-9;
			ma[pii(a[i],b[i])]=1;
		} 
		int ans=0;
		for (int i=1;i<=n;i++) {
			Q.push(pii(a[i],b[i]));
			usd.clear(); 
			usd[pii(a[i],b[i])]=1;
			while (Q.size()) {
				pii X=Q.front(); Q.pop();
//				printf("%d %d %d %d\n",a[i],b[i],X.fi,X.se);
				pii net;
				for (int j=X.fi+1;j<=17;j++)
					if (ma.count(pii(j,X.se))&&pii(j,X.se)!=pii(a[i],b[i])) {
						net=pii(2*j-X.fi,X.se);
						int flag=1;
						for (int k=j+1;k<=2*j-X.fi;k++)
							if  (ma.count(pii(k,X.se))){flag=0; break;}
						if (flag==0) break;
						if (ok(net)&&!usd.count(net)) {
							usd[net]=1;
							ans++;
							Q.push(net);
//							printf("%d%d%d%d\n")
						}
						break;
					}
				for (int j=X.fi-1;j;j--)
					if (ma.count(pii(j,X.se))&&pii(j,X.se)!=pii(a[i],b[i])) {
						net=pii(2*j-X.fi,X.se);
						int flag=1;
						for (int k=j-1;k>=2*j-X.fi;k--)
							if  (ma.count(pii(k,X.se))){flag=0; break;}
						if (flag==0) break;
						if (ok(net)&&!usd.count(net)) {
							usd[net]=1;
							ans++;
							Q.push(net);
						}
						break;
					}
				for (int j=X.se+1;j<=17;j++)
					if (ma.count(pii(X.fi,j))&&pii(X.fi,j)!=pii(a[i],b[i])) {
						net=pii(X.fi,2*j-X.se);
						int flag=1;
						for (int k=j+1;k<=2*j-X.se;k++)
							if  (ma.count(pii(X.fi,k))){flag=0; break;}
						if (flag==0) break;
						if (ok(net)&&!usd.count(net)) {
							ans++;
							Q.push(net);
						}
						break;
					}
				for (int j=X.se-1;j>-6;j--)
					if (ma.count(pii(X.fi,j))&&pii(X.fi,j)!=pii(a[i],b[i])) {
						net=pii(X.fi,2*j-X.se);
						int flag=1;
						for (int k=j-1;k>=2*j-X.se;k--)
							if  (ma.count(pii(X.fi,k))){flag=0; break;}
						if (flag==0) break;
						if (ok(net)&&!usd.count(net)) {
							usd[net]=1;
							ans++;
							Q.push(net);
						}
						break;
					}
				for (int dla=1;dla<=8;dla++)
					if (ma.count(pii(X.fi+dla,X.se+dla))&&pii(X.fi+dla,X.se+dla)!=pii(a[i],b[i])) {
						net=pii(X.fi+2*dla,X.se+2*dla);
						int flag=1;
						for (int k=1;k<=dla;k++)
							if  (ma.count(pii(X.fi+dla+k,X.se+dla+k))){flag=0; break;}
						if (flag==0) break;
						if (ok(net)&&!usd.count(net)) {
							usd[net]=1;
							ans++;
							Q.push(net);
						}
						break; 
					}
				for (int dla=1;dla<=8;dla++)
					if (ma.count(pii(X.fi-dla,X.se-dla))&&pii(X.fi-dla,X.se-dla)!=pii(a[i],b[i])) {
						net=pii(X.fi-2*dla,X.se-2*dla);
						int flag=1;
						for (int k=1;k<=dla;k++)
							if  (ma.count(pii(X.fi-dla-k,X.se-dla-k))){flag=0; break;}
						if (flag==0) break;
						if (ok(net)&&!usd.count(net)) {
							usd[net]=1;
							ans++;
							Q.push(net);
						}
						break; 
					}
			}
		}
		ma.clear();
		printf("%d\n",ans);
		ans=0;
	} 
    return 0;
}
/*
1
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3596kb

input:

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

output:

0
1
2
6
13

result:

ok 5 number(s): "0 1 2 6 13"

Test #2:

score: -100
Wrong Answer
time: 27ms
memory: 3576kb

input:

100
81
1 1
16 1
11 4
13 8
12 3
12 12
11 1
4 2
9 5
8 10
5 5
9 7
3 2
14 1
7 11
13 7
10 2
8 3
9 8
10 6
12 10
6 7
11 2
7 3
13 12
8 6
17 1
10 5
5 12
13 9
13 1
9 4
5 10
11 8
13 4
5 4
9 1
7 8
5 6
13 13
5 1
9 3
8 8
8 5
13 2
13 5
11 3
9 2
6 4
3 3
8 2
13 11
8 7
5 7
6 10
11 9
10 3
11 10
6 3
7 1
4 4
15 2
7 2
3 ...

output:

211
429
248
571
400
262
165
41
362
91
1
148
114
70
26
150
425
331
10
232
93
210
290
18
111
263
360
538
188
89
248
313
25
8
113
198
458
317
53
179
308
49
10
176
89
205
30
156
373
131
219
333
0
116
122
61
22
5
72
179
185
27
512
183
228
4
55
0
265
110
110
459
0
405
82
121
79
394
73
31
527
386
6
215
94
...

result:

wrong answer 1st numbers differ - expected: '190', found: '211'
English 繁體中文 简体中文

Server Time: 2024-12-02 19:59:52 | OpenSource Project