QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#832389 | #8355. T3 | chenxinyang2006# | 0 | 332ms | 9356kb | C++23 | 4.3kb | 2024-12-25 21:03:54 | 2024-12-25 21:04:02 |
Judging History
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