QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#832389#8355. T3chenxinyang2006#0 332ms9356kbC++234.3kb2024-12-25 21:03:542024-12-25 21:04:02

Judging History

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

  • [2024-12-25 21:04:02]
  • 评测
  • 测评结果:0
  • 用时:332ms
  • 内存:9356kb
  • [2024-12-25 21:03:54]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n;
int L[505],R[505],U[505],D[505],a[505],A[505][505],ord[505],ans[505][505];
//[0] 上,[1] 下,[2] 左,[3] 右

int cur[505][505];
void Set(int x,int y){
	if(ans[x][y] <= 1){
		cur[x][y] = y;
	}else{
		cur[x][y] = x;
	}
}

vector <pii> sta;
int vis[505][505],succ;
void dfs(int x,int y){
	if(vis[x][y]){
		per(i,SZ(sta) - 2,0) swap(ans[sta[i].first][sta[i].second],ans[sta[i + 1].first][sta[i + 1].second]);
		succ = 1;
		return;
	}
	vis[x][y] = 1;
	sta.eb(x,y);
	while(!succ){
		if(!ans[x][y]){
			if(!cur[x][y]) break;
			cur[x][y]--;
			dfs(cur[x][y],y);
		}else if(ans[x][y] == 1){
			if(cur[x][y] > n) break;
			cur[x][y]++;
			dfs(cur[x][y],y);
		}else if(ans[x][y] == 2){
			if(!cur[x][y]) break;
			cur[x][y]--;
			dfs(x,cur[x][y]);
		}else{
			if(cur[x][y] > n) break;
			cur[x][y]++;
			dfs(x,cur[x][y]);
		}
	}
	
	sta.pop_back();
	vis[x][y] = 0;
}

void slv(){
	rep(i,1,n){
		rep(j,1,n) Set(i,j);
	}
/*	rep(i,1,n){
		rep(j,1,n) printf("%d",ans[i][j]);
		printf("\n");
	}*/

	rep(i,1,n){
		rep(j,1,n){
			while(1){
				if(ans[i][j] % 2 == 0){
					if(!cur[i][j]) break;
					succ = 0;
					dfs(i,j);
				}else{
					if(cur[i][j] > n) break;
					succ = 0;
					dfs(i,j);
				}
				assert(sta.empty());
/*				printf("try dfs succ=%d\n",succ);
				rep(p,1,n){
					rep(q,1,n) printf("%d",ans[p][q]);
					printf("\n");
				}*/
			}
		}
	}
}

bool cmp(int x,int y){
	return a[x] > a[y];
}
int fail[505][505],inq[505][505];
queue <pii> Q;
void psh(int x,int y){
	if(fail[x][y] || inq[x][y]) return;
	inq[x][y] = 1;
	Q.push(mkp(x,y));
}

int main(){
#ifdef cxy
	freopen("test.in","r",stdin);
#endif
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&U[i]);
	rep(i,1,n) scanf("%d",&D[i]);
	rep(i,1,n) scanf("%d",&L[i]);
	rep(i,1,n) scanf("%d",&R[i]);

	rep(i,1,n) a[i] = U[i] + D[i];
	rep(i,1,n){
		rep(j,1,n) ord[j] = j;
		sort(ord + 1,ord + n + 1,cmp);
		if(U[i] + D[i] > n){
			printf("NO\n");
			return 0;
		}
		rep(j,1,n - L[i] - R[i]){
			if(!a[ord[j]]){
				printf("NO\n");
				return 0;
			}
			a[ord[j]]--;
			A[i][ord[j]] = 1;
		}
	}
	rep(i,1,n){
		int pos = 1;
		while(L[i]){
			while(A[i][pos]) pos++;
			ans[i][pos] = 2;
			pos++;
			L[i]--;
		}
		pos = n;
		while(R[i]){
			while(A[i][pos]) pos--;
			ans[i][pos] = 3;
			pos--;
			R[i]--;
		}
	}
	rep(i,1,n){
		int pos = 1;
		while(U[i]){
			while(!A[pos][i]) pos++;
			ans[pos][i] = 0;
			pos++;
			U[i]--;
		}
		pos = n;
		while(D[i]){
			while(!A[pos][i]) pos--;
			ans[pos][i] = 1;
			pos--;
			D[i]--;
		}
	}

	slv();
	rep(i,1,n){
		rep(j,1,n){
			if(!ans[i][j]){
				fail[i][j] = i - 1;
			}else if(ans[i][j] == 1){
				fail[i][j] = n - i;
			}else if(ans[i][j] == 2){
				fail[i][j] = j - 1;
			}else{
				fail[i][j] = n - j;
			}
			psh(i,j);
		}
	}

	while(!Q.empty()){
		pii temp = Q.front();
		Q.pop();
		int x = temp.first,y = temp.second;
		if(!ans[x][y]) printf("U%d\n",y);
		else if(ans[x][y] == 1) printf("D%d\n",y);
		else if(ans[x][y] == 2) printf("L%d\n",x);
		else printf("R%d\n",x);
		rep(p,x + 1,n){
			if(!ans[p][y]){
				fail[p][y]--;
				psh(p,y);
			}
		}
		rep(p,1,x - 1){
			if(ans[p][y] == 1){
				fail[p][y]--;
				psh(p,y);
			}
		}
		rep(q,y + 1,n){
			if(ans[x][q] == 2){
				fail[x][q]--;
				psh(x,q);
			}
		}
		rep(q,1,y - 1){
			if(ans[x][q] == 3){
				fail[x][q]--;
				psh(x,q);
			}
		}
	}
	return 0; 
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 11
Accepted
time: 0ms
memory: 7916kb

input:

1
0
1
0
0

output:

D1

result:

ok OK

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 7936kb

input:

3
0 0 1
1 1 1
0 1 0
1 2 1

output:

L1
R1
R2
D2
D3
R1
R3
U2
D1

result:

wrong answer WA

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 143ms
memory: 9084kb

input:

290
28 35 25 29 26 23 36 36 24 39 27 36 24 26 31 28 30 27 25 32 37 26 38 20 31 30 30 35 33 24 25 27 20 26 32 26 33 38 25 29 27 34 25 31 21 22 33 33 24 24 31 31 26 31 25 28 33 27 30 27 24 30 29 26 32 36 20 31 28 23 22 23 37 32 32 27 33 30 27 42 25 31 25 25 26 32 25 35 28 27 33 26 35 39 23 22 26 29 35...

output:

L1
L2
L3
L4
L5
L6
L7
L8
L9
L10
L11
L12
L13
L14
L15
L16
L17
L18
L19
L20
L21
L22
L23
L24
L25
L26
L27
L28
L29
L30
L31
L33
L34
L35
L36
L38
L39
L40
L41
L42
L43
L44
L45
L47
L48
L49
L50
L51
L52
L54
L55
L56
L57
L58
L59
L60
L62
L63
L64
L65
L66
L67
L68
L69
L71
L72
L73
L75
L76
L77
L78
L79
L80
L81
L82
L83
L85
L...

result:

wrong answer WA

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 132ms
memory: 9356kb

input:

289
30 29 31 35 25 34 26 28 25 25 44 26 33 30 27 30 33 37 26 27 43 28 28 40 31 36 21 26 35 28 31 29 41 25 30 25 35 28 38 24 26 26 24 24 25 27 18 44 31 24 37 28 26 31 27 32 29 24 24 32 20 35 26 39 30 28 33 30 27 28 37 35 29 22 27 27 31 30 25 31 31 22 30 34 33 31 30 29 41 26 38 36 28 28 21 22 31 34 32...

output:

L1
U11
R1
L2
R2
L3
R3
L4
R4
L5
R5
L6
R6
L7
R7
L8
R8
L9
R9
L10
R10
L11
R11
L12
R12
L13
R13
L14
R14
L15
R15
L16
R16
L17
R17
L18
R18
L19
R19
R20
R21
L22
R22
L23
R23
L24
R24
L25
R25
R26
L27
R27
L28
R28
L29
R29
L30
R30
L31
R31
R32
L33
R33
L34
R34
L35
R35
L36
R36
L37
R37
L38
R38
R39
L40
R40
L41
R41
L42
R4...

result:

wrong answer WA

Subtask #4:

score: 0
Wrong Answer

Test #31:

score: 25
Accepted
time: 1ms
memory: 5876kb

input:

1
1
0
0
0

output:

U1

result:

ok OK

Test #32:

score: 0
Wrong Answer
time: 1ms
memory: 7924kb

input:

2
0 1
0 1
0 0
1 1

output:

U1
R1
D2
R2

result:

wrong answer WA

Subtask #5:

score: 0
Wrong Answer

Test #77:

score: 0
Wrong Answer
time: 332ms
memory: 9052kb

input:

299
72 66 62 73 80 85 70 93 79 88 77 72 67 70 73 84 77 62 80 77 88 63 69 76 73 91 64 76 75 65 74 71 71 68 81 80 74 77 69 75 73 87 90 82 86 79 76 83 69 72 73 73 75 78 76 80 66 76 67 75 72 71 77 63 80 68 82 63 74 67 74 72 73 76 71 72 66 78 74 65 69 80 76 71 72 74 77 70 85 60 65 89 66 64 77 63 78 82 80...

output:

U1
U2
U5
U6
U8
U9
U10
U14
U15
U16
R1
L2
R2
R3
R4
R5
L6
R6
R7
L8
R8
R9
L10
R10
L11
R11
R12
L13
R13
L14
R14
R15
R16
L17
R17
R18
L19
R19
R20
L21
R21
L22
R22
R23
L24
R24
R25
L26
R26
R27
R28
R29
L30
R30
L31
R31
R32
L33
R33
R34
L35
R35
R36
R37
R38
R39
R40
L41
R41
R42
R43
R44
R45
R46
R47
R48
R49
R50
R51
R5...

result:

wrong answer WA