QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#807744 | #9564. Hey, Have You Seen My Kangaroo? | alexz1205 | TL | 291ms | 26120kb | C++20 | 4.1kb | 2024-12-10 11:01:37 | 2024-12-10 11:01:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int NM = 2e5, K = 200;
typedef long long int lint;
typedef complex<int> vect;
typedef set<vect, decltype([](vect a, vect b){return (array<int,2>){a.real(), a.imag()} < (array<int, 2>){b.real(), b.imag()};})> setV;
int n, m, k;
template<typename T, size_t SIZE>
struct Multarr{
size_t N, M;
T data[SIZE];
Multarr(){
N = n;
M = m;
}
Multarr(int N, int M){
this->N = N;
this->M = M;
memset(data, 0, sizeof(data));
}
T* operator[](size_t i){
return &data[i*M];
}
T& operator[](vect cur){
return data[cur.real()*M + cur.imag()];
}
};
char buff[K+5];
int c1[K], c2[K];
int change[K];
Multarr<char, 2*NM> grid;
Multarr<int, NM> req;
Multarr<vect, NM> nex;
Multarr<setV, NM> con;
void setUpArrs(){
grid.N = n;
grid.M = m;
memset(grid.data, 0, sizeof(grid.data));
req.N = n;
req.M = m;
memset(req.data, 0, sizeof(req.data));
nex.N = n;
nex.M = m;
}
map<char, vect> dir = {{'U', vect(-1, 0)}, {'D', vect(1, 0)}, {'L', vect(0, -1)}, {'R', vect(0, 1)}};
vect move(vect cur, vect mov){
vect v = cur+mov;
v = vect(min(max(v.real(), 0), n-1), min(max(v.imag(), 0), m-1));
if (grid[v] != '0'){
return v;
}
return cur;
}
int ans[NM+1];
int main(){
scanf("%d %d %d", &n, &m, &k);
scanf("%s", buff);
setUpArrs();
for (int x = 0; x < n; x ++){
scanf("%s", grid[x]);
}
size_t sz = 0;
for (int x = 0; x < n; x ++){
for (int y = 0; y < m; y ++){
if (grid[x][y] != '0'){
sz ++;
vect cur(x, y);
for (int z = 0; z < k; z ++){
cur = move(cur, dir[buff[z]]);
}
nex[x][y] = cur;
// cout << vect(x, y) << " " << cur << endl;
con[cur].insert(vect(x, y));
req[cur] ++;
}
}
}
vector<vect> rem;
for (int x = 0; x < n; x ++){
for (int y = 0; y < m; y ++){
if (grid[x][y] != '0'){
vect cur(x, y);
if (!req[cur]) rem.push_back(cur);
}
}
}
memset(ans, -1, sizeof(ans));
memset(ans+sz, 0, sizeof(ans) - sz*sizeof(int));
int mov = 0;
size_t i = sz-1;
{
setV inter;
for (int x = 0; x < n; x ++){
for (int y = 0; y < m; y ++){
if (req[x][y] >= 2){
inter.insert(vect(x, y));
}
}
}
memset(change, 0, sizeof(change));
setV spect;
for (vect v: inter){
for (vect v2: con[v]){
spect.insert(v2);
}
}
for (int x = 0; x < k; x ++){
setV newSpect;
for (vect cur: spect){
vect v = move(cur, dir[buff[x]]);
newSpect.insert(v);
}
change[x] = spect.size() - newSpect.size();
swap(spect, newSpect);
}
}
while (!rem.empty()){
// for (int x = 0; x < k; x ++){
// cout << change[x] << " ";
// }
// cout << endl;
for (int x = 0; x < k; x ++){
if (change[x] < 0){
exit(-1);
}
if (sz < (size_t)change[x]){
exit(0);
}
sz -= change[x];
while (i >= sz){
ans[i--] = mov*k + x + 1;
}
}
setV recalc;
vector<vect> nexRem;
for (vect cur: rem){
if (req[nex[cur]] >= 2){
recalc.insert(nex[cur]);
}
}
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
{
setV spect;
for (vect v: recalc){
for (vect v2: con[v]){
spect.insert(v2);
}
}
for (int x = 0; x < k; x ++){
setV newSpect;
for (vect cur: spect){
vect v = move(cur, dir[buff[x]]);
newSpect.insert(v);
}
c1[x] = spect.size() - newSpect.size();
swap(spect, newSpect);
}
}
for (vect cur: rem){
if (req[nex[cur]] == 2){
recalc.erase(nex[cur]);
}
req[nex[cur]] --;
con[nex[cur]].erase(cur);
if (!req[nex[cur]]) nexRem.push_back(nex[cur]);
}
{
setV spect;
for (vect v: recalc){
for (vect v2: con[v]){
spect.insert(v2);
}
}
for (int x = 0; x < k; x ++){
setV newSpect;
for (vect cur: spect){
vect v = move(cur, dir[buff[x]]);
newSpect.insert(v);
}
c2[x] = spect.size() - newSpect.size();
swap(spect, newSpect);
}
}
for (int x = 0; x < k; x ++){
change[x] -= c1[x] - c2[x];
}
swap(nexRem, rem);
mov ++;
}
for (int x = 1; x <= n*m; x ++){
printf("%d\n", ans[x]);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 16716kb
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: 4ms
memory: 16664kb
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: 0ms
memory: 16768kb
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: 291ms
memory: 26120kb
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: -100
Time Limit Exceeded
input:
2 100000 200 UULDRDLURDLDDRDRDUULDLUUULLRURLUUDDDRURURLLRRUDLDDDUDDRRUUURDDULURURLRULLUDLULURUUDURLDRRRDULRDLRRLDUUUDDUUDUDRDRUDLDRRUDRDLDRDLDRRDLRRDRDLRRLUDUDRULLRRLDDLUDDULDRLLLDLURRDDULDDUDULLRRRUURLRRRLURDLRLU 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111...