QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#832405 | #8355. T3 | chenxinyang2006# | 15 | 138ms | 9172kb | C++23 | 4.8kb | 2024-12-25 21:12:19 | 2024-12-25 21:12:19 |
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] = x;
}else{
cur[x][y] = y;
}
}
vector <pii> sta;
int vis[505][505],succ;
void dfs(int x,int y){
// printf("(%d,%d)\n",x,y);
if(vis[x][y]){
// printf("succful find circle:\n");
// for(pii I:sta) printf("%d %d\n",I.first,I.second);
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]){
// assert(cur[x][y] >= 1);
cur[x][y]--;
if(cur[x][y] <= 0) break;
dfs(cur[x][y],y);
}else if(ans[x][y] == 1){
// assert(cur[x][y] <= n);
cur[x][y]++;
if(cur[x][y] > n) break;
dfs(cur[x][y],y);
}else if(ans[x][y] == 2){
// assert(cur[x][y] >= 1);
cur[x][y]--;
if(cur[x][y] <= 0) break;
dfs(x,cur[x][y]);
}else{
// assert(cur[x][y] <= n);
cur[x][y]++;
if(cur[x][y] > n) break;
dfs(x,cur[x][y]);
}
}
sta.pop_back();
vis[x][y] = 0;
}
void dbg(){
printf("curans:\n");
rep(i,1,n){
rep(j,1,n) printf("%d",ans[i][j]);
printf("\n");
rep(j,1,n) assert(!vis[i][j]);
}
}
void slv(){
rep(i,1,n){
rep(j,1,n) Set(i,j);
}
// dbg();
rep(i,1,n){
rep(j,1,n){
while(1){
// printf("start dfs from (%d,%d)\n",i,j);
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());
// dbg();
}
}
}
}
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;
rep(k,1,L[i]){
while(A[i][pos]) pos++;
ans[i][pos] = 2;
pos++;
}
pos = n;
rep(k,1,R[i]){
while(A[i][pos]) pos--;
ans[i][pos] = 3;
pos--;
}
}
rep(i,1,n){
int pos = 1;
rep(k,1,U[i]){
while(!A[pos][i]) pos++;
ans[pos][i] = 0;
pos++;
}
pos = n;
rep(k,1,D[i]){
while(!A[pos][i]) pos--;
ans[pos][i] = 1;
pos--;
}
}
slv();
rep(i,1,n){
int temp = L[i] + R[i];
rep(j,1,n) if(ans[i][j] >= 2) temp--;
assert(!temp);
}
rep(i,1,n){
int temp = U[i] + D[i];
rep(j,1,n) if(ans[j][i] < 2) temp--;
assert(!temp);
}
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);
}
}
}
rep(i,1,n){
rep(j,1,n) assert(!fail[i][j]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 11
Accepted
time: 1ms
memory: 7884kb
input:
1 0 1 0 0
output:
D1
result:
ok OK
Test #2:
score: 11
Accepted
time: 0ms
memory: 7924kb
input:
3 0 0 1 1 1 1 0 1 0 1 2 1
output:
U3 L2 R2 D2 D3 R1 R2 R3 D1
result:
ok OK
Test #3:
score: 0
Time Limit Exceeded
input:
3 0 0 2 2 0 0 1 0 2 1 1 0
output:
result:
Subtask #2:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 134ms
memory: 8952kb
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 U10 U21 U23 U38 U66 U73 U80 U94 U103 U131 U142 U156 U183 U199 U213 U226 U228 U232 U246 U253 U270 U272 U278 U280 U287 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 ...
result:
ok OK
Test #12:
score: 15
Accepted
time: 121ms
memory: 8836kb
input:
277 53 51 63 63 45 55 51 56 53 55 59 51 54 60 48 59 62 45 51 55 61 55 57 51 52 61 47 59 61 52 50 51 44 59 61 59 45 47 66 55 71 59 55 66 63 56 50 56 55 53 53 51 58 55 48 60 67 54 58 49 48 52 63 52 61 66 52 64 57 61 50 61 58 58 48 56 76 56 49 55 57 52 44 62 59 55 50 47 53 52 69 51 56 55 64 52 49 59 55...
output:
L1 U3 U4 U17 U21 U26 U29 U35 U39 U41 U44 U45 U57 U63 U65 U66 U68 U70 U72 U77 U84 U91 U95 U106 U107 U118 U138 U141 U145 U151 U156 U157 U159 U164 U165 U167 U174 U178 U179 U183 U191 U220 U221 U222 U223 U224 U233 U236 U237 U239 U241 U251 U252 U253 U256 U262 U264 U268 U272 U274 U275 U276 L2 L3 L4 L5 L6 L...
result:
ok OK
Test #13:
score: 15
Accepted
time: 131ms
memory: 8952kb
input:
282 100 80 83 92 99 86 81 73 90 97 79 88 78 90 93 75 80 95 88 75 73 86 84 76 86 80 89 87 84 81 78 84 75 86 76 81 85 101 69 88 80 86 86 97 83 83 71 94 82 98 79 79 82 84 96 83 90 82 69 82 90 80 85 89 99 76 94 87 85 78 74 93 69 85 87 75 87 95 77 77 86 71 88 73 91 88 72 86 85 78 88 82 82 96 90 79 79 82 ...
output:
U1 U4 U5 U9 U10 U12 U14 U15 U18 U19 U27 U38 U40 U44 U48 U50 U55 U57 U61 U64 U65 U67 U68 U72 U75 U78 U83 U85 U86 U91 U94 U95 U99 U100 U102 U103 U104 U109 U110 U113 U118 U120 U123 U124 U129 U130 U132 U134 U136 U137 U142 U148 U150 U154 U156 U158 U160 U165 U167 U171 U172 U175 U176 U177 U179 U180 U182 U1...
result:
ok OK
Test #14:
score: 15
Accepted
time: 138ms
memory: 8952kb
input:
287 98 119 107 123 117 117 121 115 127 128 115 133 111 117 110 96 91 113 110 110 114 105 114 109 98 108 120 129 113 103 99 119 104 123 100 111 117 118 125 126 124 123 114 105 121 108 128 107 124 126 118 116 114 125 119 103 111 119 129 120 121 109 113 108 109 122 119 119 116 119 113 122 124 117 126 1...
output:
L1 U2 U4 U5 U7 U9 U10 U12 U27 U28 U32 U34 U37 U38 U39 U40 U41 U42 U45 U47 U49 U50 U51 U54 U55 U58 U59 U60 U61 U66 U67 U68 U70 U72 U73 U74 U75 U76 U77 U78 U79 U85 U86 U90 U91 U94 U95 U97 U98 U100 U101 U109 U113 U114 U115 U116 U119 U120 U121 U122 U123 U125 U127 U128 U129 U132 U133 U136 U137 U140 U146 ...
result:
ok OK
Test #15:
score: 15
Accepted
time: 110ms
memory: 8948kb
input:
265 144 139 128 130 134 135 140 122 129 143 129 132 132 135 120 135 146 138 129 132 111 123 154 138 128 124 125 135 134 141 130 127 146 123 131 133 122 142 140 146 140 141 128 119 133 134 137 148 123 134 142 127 124 137 130 132 136 128 142 126 134 126 138 137 133 141 119 137 146 137 136 126 141 127 ...
output:
U1 U2 U5 U6 U7 U10 U14 U16 U17 U18 U23 U24 U28 U29 U30 U33 U38 U39 U40 U41 U42 U46 U47 U48 U50 U51 U54 U57 U59 U61 U63 U64 U66 U68 U69 U70 U71 U73 U76 U78 U83 U84 U85 U87 U88 U89 U90 U91 U92 U93 U94 U95 U97 U98 U100 U103 U104 U106 U108 U109 U114 U115 U116 U119 U121 U122 U123 U132 U133 U135 U139 U140...
result:
ok OK
Test #16:
score: 15
Accepted
time: 2ms
memory: 6312kb
input:
286 235 245 221 241 222 248 226 244 228 207 234 229 241 261 209 231 222 203 225 230 256 224 236 243 222 246 235 243 247 234 241 255 232 234 211 258 249 238 252 237 240 221 244 223 212 240 259 261 235 264 238 205 224 223 238 222 199 225 222 217 236 220 212 204 230 253 221 214 195 216 219 239 220 233 ...
output:
NO
result:
ok OK
Test #17:
score: 15
Accepted
time: 114ms
memory: 8896kb
input:
268 187 183 183 184 179 189 177 173 176 186 183 182 187 175 185 218 176 191 195 183 182 197 182 195 195 183 185 193 205 182 192 179 183 176 190 185 195 182 189 189 196 184 194 184 199 189 190 190 191 201 197 196 190 186 186 197 188 190 188 171 191 186 181 188 170 188 176 188 190 190 187 181 190 187 ...
output:
U1 U4 U6 U10 U13 U15 U16 U18 U19 U22 U24 U25 U27 U28 U29 U31 U35 U36 U37 U39 U40 U41 U42 U43 U44 U45 U46 U47 U48 U49 U50 U51 U52 U53 U54 U55 U56 U57 U58 U59 U61 U62 U64 U66 U68 U69 U70 U71 U73 U74 U75 U76 U77 U79 U80 U82 U84 U85 U86 U88 U89 U90 U91 U93 U95 U98 U99 U100 U102 U103 U104 U105 U106 U107 ...
result:
ok OK
Test #18:
score: 15
Accepted
time: 101ms
memory: 8976kb
input:
261 204 204 215 204 209 212 197 219 216 205 210 208 216 205 207 203 217 203 209 208 211 207 210 213 200 206 213 208 214 205 200 220 206 210 213 209 206 207 207 201 212 213 212 206 225 210 196 221 205 217 202 206 212 205 196 218 205 209 194 206 199 204 219 204 222 208 208 210 195 208 215 211 201 206 ...
output:
U1 U2 U3 U4 U5 U6 U8 U9 U10 U11 U12 U13 U14 U15 U16 U17 U18 U19 U20 U21 U22 U23 U24 U26 U27 U28 U29 U30 U32 U33 U34 U35 U36 U37 U38 U39 U41 U42 U43 U44 U45 U46 U48 U49 U50 U52 U53 U54 U56 U57 U58 U60 U62 U63 U64 U65 U66 U67 U68 U70 U71 U72 U74 U76 U77 U78 U79 U80 U81 U83 U84 U86 U87 U90 U91 U92 U93 ...
result:
ok OK
Test #19:
score: 15
Accepted
time: 130ms
memory: 9172kb
input:
281 251 252 254 244 260 254 254 245 251 258 258 253 256 263 249 256 252 253 247 253 250 249 243 248 264 246 246 264 242 256 245 258 257 251 252 247 252 259 251 253 252 246 255 261 255 249 251 250 255 255 257 246 251 254 250 255 256 258 256 257 254 254 252 254 263 258 262 253 255 250 250 254 245 264 ...
output:
U1 U2 U3 U5 U6 U7 U9 U10 U11 U12 U13 U14 U15 U16 U17 U18 U19 U20 U21 U22 U24 U25 U26 U27 U28 U30 U32 U33 U34 U35 U36 U37 U38 U39 U40 U41 U42 U43 U44 U45 U46 U47 U48 U49 U50 U51 U52 U53 U54 U55 U56 U57 U58 U59 U60 U61 U62 U63 U64 U65 U66 U67 U68 U69 U70 U71 U72 U74 U75 U76 U77 U78 U79 U80 U82 U83 U84...
result:
ok OK
Test #20:
score: 15
Accepted
time: 74ms
memory: 8448kb
input:
253 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
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 L32 L33 L34 L35 L36 L37 L38 L39 L40 L41 L42 L43 L44 L45 L46 L47 L48 L49 L50 L51 L52 L53 L54 L55 L56 L57 L58 L59 L60 L61 L62 L63 L64 L65 L66 L67 L68 L69 L70 L71 L72 L73 L74 L75 L76 L77 L...
result:
ok OK
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #31:
score: 25
Accepted
time: 0ms
memory: 7916kb
input:
1 1 0 0 0
output:
U1
result:
ok OK
Test #32:
score: 25
Accepted
time: 1ms
memory: 7920kb
input:
2 0 1 0 1 0 0 1 1
output:
U2 D2 R1 R2
result:
ok OK
Test #33:
score: 25
Accepted
time: 1ms
memory: 7916kb
input:
3 0 1 0 0 1 2 2 1 0 0 1 1
output:
L1 U2 L2 D2 D3 L1 D3 R3 R2
result:
ok OK
Test #34:
score: 0
Time Limit Exceeded
input:
9 2 1 3 4 3 3 2 3 2 2 4 2 1 1 2 4 2 2 4 0 3 3 1 1 2 3 2 0 2 2 2 2 4 1 2 4
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #77:
score: 0
Time Limit Exceeded
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...