QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735354 | #9564. Hey, Have You Seen My Kangaroo? | MiniLong | WA | 438ms | 19124kb | C++20 | 4.9kb | 2024-11-11 19:27:00 | 2024-11-11 19:27:01 |
Judging History
answer
#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
#ifdef ONLINE_JUDGE
char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
#define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
#else
#define get() getchar()
#endif
template<typename T> inline void read(T &t){
T x = 0, f = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
t = x * f;
}
template<typename T, typename ... Args> inline void read(T &t, Args&... args){
read(t);
read(args...);
}
template<typename T> void write(T t){
if(t < 0) putchar('-'), t = -t;
if(t >= 10) write(t / 10);
putchar(t % 10 + '0');
}
template<typename T, typename ... Args> void write(T t, Args... args){
write(t), putchar(' '), write(args...);
}
template<typename T> void writeln(T t){
write(t);
puts("");
}
template<typename T> void writes(T t){
write(t), putchar(' ');
}
#undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
const ll mod = 998244353;
ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
void add(ll &x, ll y){x = (x + y) % mod;}
void mul(ll &x, ll y){x = x * y % mod;}
ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 2e5 + 5, M = 205, inf = 0x3f3f3f3f;
int n, m, k, s[M];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int code(int x, int y){return (x - 1) * m + y;}
PII decode(int x){return make_pair((x - 1) / m + 1, (x - 1) % m + 1);}
char ch[N];
vector<bool> a[N];
vector<int> v[N];
bool vis[N];
int nxt[N], in[N], h[N];
void topo(){
_rep(i, 1, n) _rep(j, 1, m) if(a[i][j]) in[nxt[code(i, j)]]++;
queue<int> q;
_rep(i, 1, n) _rep(j, 1, m) if(a[i][j] && !in[code(i, j)]) q.push(code(i, j));
vector<int> p;
while(q.size()){
int u = q.front(); q.pop();
vis[u] = 1, p.pb(u);
if(!--in[nxt[u]]) q.push(nxt[u]);
}
for(auto &i : p) h[nxt[i]] = max(h[nxt[i]], h[i] + 1);
_rep(i, 1, n) if(!vis[i]) h[i] = inf;
}
int ans[N];
int main(){
read(n, m, k), scanf("%s", ch + 1);
_rep(i, 1, k) s[i] = ch[i] == 'U' ? 0 : (ch[i] == 'D' ? 1 : (ch[i] == 'L' ? 2 : 3));
int tot = 0;
_rep(i, 1, n){
scanf("%s", ch + 1), a[i].resize(m + 1);
_rep(j, 1, m) a[i][j] = ch[j] - '0', tot += a[i][j];
}
_rep(i, 1, n) _rep(j, 1, m){
if(!a[i][j]) continue;
int x = i, y = j;
_rep(p, 1, k){
int nx = x + dx[s[p]], ny = y + dy[s[p]];
if(nx < 1 || ny < 1 || nx > n || ny > m || !a[nx][ny]) continue;
x = nx, y = ny;
}
nxt[code(i, j)] = code(x, y);
}
topo();
vector<PII> p, vt; vector<int> lst(n * m + 1, 0);
_rep(i, 1, n) _rep(j, 1, m) if(a[i][j]) p.pb({code(i, j), code(i, j)});
_rep(o, 1, k){
vector<int> cur; vector<PII> np;
for(auto &[i, j] : p){
PII t = decode(i); int x = t.fi, y = t.se;
int nx = x + dx[s[o]], ny = y + dy[s[o]];
if(nx < 1 || ny < 1 || nx > n || ny > m || !a[nx][ny]){nx = x, ny = y;}
if(lst[code(nx, ny)]){
int u = j, v = lst[code(nx, ny)];
vt.pb({min(h[u], h[v]), o});
if(h[u] > h[v]) lst[code(nx, ny)] = u;
}else{
cur.pb(code(nx, ny));
lst[code(nx, ny)] = j;
}
}
for(auto &i : cur) np.pb({i, lst[i]}), lst[i] = 0;
swap(p, np);
}
vector<int> cur;
for(auto &i : vt){
_rep(o, 0, i.fi) cur.pb(o * k + i.se);
}
sort(cur.begin(), cur.end());
vector<int> ans(n * m + 1, -1);
int res = tot, len = cur.size(); _rep(i, tot, n * m) ans[i] = 0;
_rep(i, 0, len - 1){
int j = i;
while(j < len - 1 && cur[j + 1] == cur[i]) j++;
_rep(k, i, j) ans[--res] = cur[i];
i = j;
}
_rep(i, 1, n * m) writeln(ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5736kb
input:
3 3 6 ULDDRR 010 111 010
output:
-1 4 2 1 0 0 0 0 0
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
3 3 6 ULDDRR 010 111 011
output:
7 4 2 1 1 0 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 7820kb
input:
1 5 1 R 11111
output:
4 3 2 1 0
result:
ok 5 number(s): "4 3 2 1 0"
Test #4:
score: 0
Accepted
time: 376ms
memory: 17104kb
input:
1 200000 200 RDRLDRULURDLDRULLRULLRRULRULRDLLDLRUDDLRURLURLULDRUUURDLUDUDLLLLLURRDURLUDDRRLRRURUUDDLLDDUUUDUULRLRUDULRRUURUDDDDLULULLLLLLLLLLLUDURLURLRLLRRRURUURLUDULDUULRRLULLRUDRDRUUDDRUDRDLLDLURDDDURLUULDRRDLDD 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
3999923 3999865 3999864 3999740 3999729 3999728 3999727 3999726 3999725 3999724 3999723 3999665 3999664 3999540 3999529 3999528 3999527 3999526 3999525 3999524 3999523 3999465 3999464 3999340 3999329 3999328 3999327 3999326 3999325 3999324 3999323 3999265 3999264 3999140 3999129 3999128 3999127 3999...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 284ms
memory: 15300kb
input:
2 100000 200 UULDRDLURDLDDRDRDUULDLUUULLRURLUUDDDRURURLLRRUDLDDDUDDRRUUURDDULURURLRULLUDLULURUUDURLDRRRDULRDLRRLDUUUDDUUDUDRDRUDLDRRUDRDLDRDLDRRDLRRDRDLRRLUDUDRULLRRLDDLUDDULDRLLLDLURRDDULDDUDULLRRRUURLRRRLURDLRLU 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 384513 384490 384313 384290 384113 384090 383913 383890 383713 383690 383513 383490 383313 383290 383113 383090 382913 382890 382713 382690 382513 382490 382313 382290 382113 382090 381913 381890 381713 381690 381513 381490 381313 381290 381113 381090 380...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 252ms
memory: 16620kb
input:
5 40000 200 URDDRRUDURLDLUUDUUDDLRRRURULURDRRURRURULUULRRLDLLDUURRDRUULRULULUDRURRRURDDLLDDRLLLUDUDLLDDULUUUULDLDUDLULLDRURRDRDULURLLLUDLRRRDRLUDDUURULURRRDLDRUDLURUUULDLURDDDRRLLLDLRRDLDLDRRURRRRDLRRLLULRRLDUULD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1000036 999836 999636 999436 999236 999036 998836 998636 998436 998236 998036 997836 997636 997436 997236 997036 996836 996636 996436 996236 996036 995836 995636 995436 995236 995036 994836 994636 994436 994236 994036 993836 993636 993436 993236 993036 992836 992636 992436 992236 992036 991836 99163...
result:
ok 200000 numbers
Test #7:
score: 0
Accepted
time: 257ms
memory: 14888kb
input:
10 20000 200 UULRURURUDRUULRRRDDDULUURRDUURDLDLLURRDUDDRDULRDURLDDLRRRRRRURLLUUURURDDUDDLLRDRLDDDDRULDRLLDUDLLLUDRURLDDLRRULDRRLLRRRDLRUDDDRRLDLRUDRUUDDDLUDULLDLUDUDUUUDLLRUURRLRLLDLLLLRLLRRDRRLLUDDURDRRDDULLDDULR 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
571658 571458 571258 571058 570858 570658 570458 570258 570058 569858 569658 569458 569258 569058 568858 568658 568458 568258 568058 567858 567658 567458 567258 567058 566858 566658 566458 566258 566058 565858 565658 565458 565258 565058 564858 564658 564458 564258 564058 563858 563658 563458 563258...
result:
ok 200000 numbers
Test #8:
score: 0
Accepted
time: 327ms
memory: 17580kb
input:
20 10000 200 UUDUUDRDLLLURLULDRULUDLRURRUUDLDLUURUDURDRUULULULUURRDDDLUDLLRDDLDULLDURLRRUULLRDULUUDDLRDLDRDLDULULRLLLLUDUUUDDLDLLRLUUDLURLULLURDDDLLLUDDDLRDULLUUDRLDLRDLRLURRUUDLRULURRLLLURRUDLDUDRLUDDRDUUULLDDUDL 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
83411 83305 83211 83105 83011 82905 82811 82705 82611 82505 82411 82305 82211 82105 82011 81905 81811 81705 81611 81505 81411 81305 81211 81105 81011 80905 80811 80705 80611 80505 80411 80305 80211 80105 80011 79905 79811 79705 79611 79505 79411 79305 79211 79105 79011 78905 78811 78705 78611 78505 ...
result:
ok 200000 numbers
Test #9:
score: 0
Accepted
time: 438ms
memory: 16932kb
input:
50 4000 200 LUDLUULUUUDUDDUDRULLDDRDRDLDUDRUUDUUUDULDUURDUUDLRUDDDURURRRUDDRUDDRURURURUDLLLDRURLLRRURRLULDDLLURULRDURDDLURURDDURDDRURRDDDULUURLUDRRUULRLURUDULLRURUUDLRDDLULUDRULDRRLRRLURDLUDDRDRLRRDDULRULDLURRRUL 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
53472 53272 53072 52872 52672 52472 52272 52072 51872 51672 51472 51272 51072 50872 50672 50472 50272 50072 49872 49672 49472 49272 49072 48872 48672 48472 48272 48072 47872 47672 47472 47272 47072 46872 46672 46472 46272 46072 45872 45672 45472 45272 45072 44872 44672 44472 44272 44072 43872 43672 ...
result:
ok 200000 numbers
Test #10:
score: 0
Accepted
time: 380ms
memory: 17552kb
input:
100 2000 200 UDULUDLDUUDDUDLURDRDLDDLLDRLLDUURUDLLUURLRLLRDLUUUURLLUDRRUDUDDLRLLLDDUUDDULRUUULLRRUUUUUDRLLUUUURDUDLUUDLUDDRRULRLRLUDLRLRRRLRULULLRLLURRUUUDRLRRRRLUURULURUUUUDURRDDDRLLLLULDUDRLDURUUDDRRRULULRLRDULD 10111111111111111111111111111111111111111111111111111111111111111110111111111100111111...
output:
-1 -1 47281 47081 46881 46681 46481 46281 46081 45881 45681 45481 45281 45081 44881 44681 44481 44281 44081 43881 43681 43481 43281 43081 42881 42681 42481 42281 42081 41881 41681 41481 41281 41081 40881 40681 40481 40281 40081 39881 39681 39481 39281 39081 38881 38681 38481 38281 38081 37881 37681 ...
result:
ok 200000 numbers
Test #11:
score: 0
Accepted
time: 381ms
memory: 18508kb
input:
200 1000 200 RLRDLDRDUDLRDULDLLURDULDLLDUDLULLLUUUDLRRRUDLUUUDDRLULRRLDLDLLDRLLLURDLDRRRLULUDDLUDUULULUULDRRURDDLUUULURULRUUDRRLRDULDUDRLDLRUDRLULLLLRLLDRDLDLRDUUUUUULUDLDRUDDUUDRLDRUDUUDLULLDDURLRULLRULDRLLRDLURR 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 10432 10232 10062 10032 9994 9887 9862 9832 9794 9687 9662 9632 9594 9487 9462 9432 9394 9287 9262 9232 9194 9087 9062 9032 8994 8887 8862 8832 8794 8687 8662 8632 8594 8487 8462 8432 8394 8287 8262 8232 8194 8135 8087 8062 8032 7994 7935 7887 7862 7832 7794 7736 7735 7687 7662 7632 7594 7553 753...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 395ms
memory: 19124kb
input:
400 500 200 RULLRRRDLUDDRLDDRDLRLDLDLUUDRUDDULRDDLDULULLRUDULRLRLRUDURDRDDDLDRUDRLRDRLRDLULLLLRURRLRRULULDLDRDDULDDUULURLRLLDUUUUDDUDURLULRLDRLDDRULUDDLLRRDDULLDLURDLDRLLULRLRUULRLLLRULRUDLRRRLURUULLLDDDUDRDLRURD 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
9541 9370 9369 9341 9244 9243 9170 9169 9141 9103 9044 9043 9039 9039 9022 8987 8970 8969 8960 8941 8903 8876 8865 8844 8843 8839 8839 8824 8822 8787 8770 8769 8760 8750 8741 8703 8676 8676 8665 8644 8643 8639 8639 8624 8622 8588 8587 8570 8569 8560 8550 8541 8503 8503 8476 8476 8465 8444 8443 8439 ...
result:
ok 200000 numbers
Test #13:
score: -100
Wrong Answer
time: 397ms
memory: 18968kb
input:
447 447 200 LULRUURRDLDUDDRDRLDDUDLRLURUDLLDDLRLRDLURURRDRDDDRRDDLLDRDDDUDULLRLURLLURULLLLRUUULDRDRRDDULULRLURDDUDURDULUURRLDURURDDUDDDDURRLRLLDLULDRURDUUURLRULURUULURURUDDRDDDDLLRRLLLDRLRDDRRLDDRULLLLRURDRUULRUU 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 22650 22450 22250 22050 21850 21650 214...
result:
wrong answer 75th numbers differ - expected: '22650', found: '-1'