QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#807744#9564. Hey, Have You Seen My Kangaroo?alexz1205TL 291ms26120kbC++204.1kb2024-12-10 11:01:372024-12-10 11:01:39

Judging History

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

  • [2024-12-10 11:01:39]
  • 评测
  • 测评结果:TL
  • 用时:291ms
  • 内存:26120kb
  • [2024-12-10 11:01:37]
  • 提交

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...

output:


result: