oj.uz

Submission #348354

# Submission time Handle Problem Language Result Execution time Memory
348354 2021-01-14T18:12:25 Z koioi.org-youngyojun 여왕벌 (KOI15_queen) C++17
101 / 100
 4591 ms 133740 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (705)
#define MAXQ (1000005)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<vector<int>> Mat;
typedef vector<vector<pii>> Mati;
pii operator + (pii a, pii b) { return {a.first+b.first, a.second+b.second}; }
pii operator - (pii a, pii b) { return {a.first-b.first, a.second-b.second}; }

int A[MAXQ], B[MAXQ], C[MAXQ];
int d[MAXN][MAXN];
char str[MAXN][MAXN][28];
int N, Q;

pii f(int l, int a, int b, int s, int e) {
	if(a+b <= s && s <= l-1) return {0, 0};
	if(a <= s && s <= a+b-1) {
		if(a <= e && e <= a+b-1) return {0, e-s+1};
		return {0, a+b-s};
	}
	if(0 <= s && s <= a-1) {
		if(0 <= e && e <= a-1) return {e-s+1, 0};
		if(a <= e && e <= a+b-1) return {a-s, e-a+1};
		return {a-s, b};
	}
	//puts("ERR BUMSOO1");
	exit(-1);
}
Mati f(int ys, int ye, int xs, int xe, Mat V) {
	const int L = ye-ys+xe-xs+1;
	/*printf("F %d %d %d %d\n", ys, ye, xs, xe);
	puts("d map");
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) printf("%d ", d[i][j]);
		puts("");
	}
	puts("V map");
	for(int i = 0; i <= L; i++) {
		for(int j = 0; j <= L; j++) printf("%d %d : %d\n", i, j, V[i][j]);
	}
	puts("\n\n");*/
	if(1 == ye-ys && 1 == xe-xs) {
		Mati ret(L+1, vector<pii>(L+1, pii(-1, -1)));
		int tmp[3] = {0, };
		for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
			if(!V[i][j]) continue;
			for(int k = 0; k < i; k++) tmp[k] = 0;
			for(int k = i; k < i+j; k++) tmp[k] = 1;
			for(int k = i+j; k < 3; k++) tmp[k] = 2;
			d[ys][xs] += tmp[1] * V[i][j];
			char c = str[ye][xe][tmp[0]*9 + tmp[1]*3 + tmp[2]];
			if('L' == c) tmp[1] = tmp[0];
			else if('U' == c) tmp[1] = tmp[2];
			pii cnt(0, 0);
			for(int k = 0; k < 3; k++) {
				if(!tmp[k]) cnt.first++;
				else if(1 == tmp[k]) cnt.second++;
			}
			ret[i][j] = cnt;
		}
	/*printf("RET F %d %d %d %d\n", ys, ye, xs, xe);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++)
		printf("%d %d : %d %d\n", i, j, ret[i][j].first, ret[i][j].second);*/
		return ret;
	}
	if(1 == ye-ys) {
		Mati ret(L+1, vector<pii>(L+1, pii(-1, -1)));
		vector<int> tmp(L, 0);
		for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
			if(!V[i][j]) continue;
			for(int k = 0; k < i; k++) tmp[k] = 0;
			for(int k = i; k < i+j; k++) tmp[k] = 1;
			for(int k = i+j; k < L; k++) tmp[k] = 2;
			for(int k = xs+1; k <= xe; k++) {
				d[ys][k-1] += tmp[k-xs] * V[i][j];
				char c = str[ye][k][tmp[k-xs-1]*9 + tmp[k-xs]*3 + tmp[k-xs+1]];
				if('L' == c) tmp[k-xs] = tmp[k-xs-1];
				else if('U' == c) tmp[k-xs] = tmp[k-xs+1];
			}
			pii cnt(0, 0);
			for(int k = 0; k < L; k++) {
				if(!tmp[k]) cnt.first++;
				else if(1 == tmp[k]) cnt.second++;
			}
			ret[i][j] = cnt;
		}
	/*printf("RET F %d %d %d %d\n", ys, ye, xs, xe);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++)
		printf("%d %d : %d %d\n", i, j, ret[i][j].first, ret[i][j].second);*/
		return ret;
	}
	if(1 == xe-xs) {
		Mati ret(L+1, vector<pii>(L+1, pii(-1, -1)));
		vector<int> tmp(L, 0);
		for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
			if(!V[i][j]) continue;
			for(int k = 0; k < i; k++) tmp[k] = 0;
			for(int k = i; k < i+j; k++) tmp[k] = 1;
			for(int k = i+j; k < L; k++) tmp[k] = 2;
			for(int k = ys+1; k <= ye; k++) {
				d[k-1][xs] += tmp[ye-k+1] * V[i][j];
				char c = str[k][xe][tmp[ye-k]*9 + tmp[ye-k+1]*3 + tmp[ye-k+2]];
				if('L' == c) tmp[ye-k+1] = tmp[ye-k];
				else if('U' == c) tmp[ye-k+1] = tmp[ye-k+2];
			}
			pii cnt(0, 0);
			for(int k = 0; k < L; k++) {
				if(!tmp[k]) cnt.first++;
				else if(1 == tmp[k]) cnt.second++;
			}
			ret[i][j] = cnt;
		}
	/*printf("RET F %d %d %d %d\n", ys, ye, xs, xe);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++)
		printf("%d %d : %d %d\n", i, j, ret[i][j].first, ret[i][j].second);*/
		return ret;
	}
	Mati ret(L+1, vector<pii>(L+1, pii(-1, -1))), ret1 = ret, pv;
	Mat Q, W(L+1, vector<int>(L+1, 0));
	int ym = (ys+ye)/2, xm = (xs+xe)/2;
	Q.resize(ym-ys+xm-xs+2, vector<int>(ym-ys+xm-xs+2, 0));
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii ret = f(L, i, j, ye-ym, ye-ys+xm-xs);
		Q[ret.first][ret.second] += V[i][j];
	}
	pv = f(ys, ym, xs, xm, Q);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii mid = f(L, i, j, ye-ym, ye-ys+xm-xs);
		pii fin = pii(i, j) - mid + pv[mid.first][mid.second];
		W[fin.first][fin.second] += V[i][j];
		ret[i][j] = fin;
	}
	swap(V, W); for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) W[i][j] = 0;
	clv(Q); Q.resize(ym-ys+xe-xm+2, vector<int>(ym-ys+xe-xm+2, 0));
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii ret = f(L, i, j, ye-ym+xm-xs, L-1);
		Q[ret.first][ret.second] += V[i][j];
	}
	pv = f(ys, ym, xm, xe, Q);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii mid = f(L, i, j, ye-ym+xm-xs, L-1);
		pii fin = pii(i, j) - mid + pv[mid.first][mid.second];
		W[fin.first][fin.second] += V[i][j];
		ret1[i][j] = fin;
	}
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(ret[i][j].first < 0) continue;
		ret[i][j] = ret1[ret[i][j].first][ret[i][j].second];
	}
	swap(V, W); for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) { ret1[i][j] = pii(-1, -1); W[i][j] = 0; }
	clv(Q); Q.resize(ye-ym+xm-xs+2, vector<int>(ye-ym+xm-xs+2, 0));
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii ret = f(L, i, j, 0, ye-ym+xm-xs);
		Q[ret.first][ret.second] += V[i][j];
	}
	pv = f(ym, ye, xs, xm, Q);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii mid = f(L, i, j, 0, ye-ym+xm-xs);
		pii fin = pii(i, j) - mid + pv[mid.first][mid.second];
		W[fin.first][fin.second] += V[i][j];
		ret1[i][j] = fin;
	}
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(ret[i][j].first < 0) continue;
		ret[i][j] = ret1[ret[i][j].first][ret[i][j].second];
	}
	swap(V, W); for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) { ret1[i][j] = pii(-1, -1); W[i][j] = 0; }
	clv(Q); Q.resize(ye-ym+xe-xm+2, vector<int>(ye-ym+xe-xm+2, 0));
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii ret = f(L, i, j, xm-xs, ye-ym+xe-xs);
		//pii ret = f(L, i, j, ye-ym+xm-xs, L-1);
		Q[ret.first][ret.second] += V[i][j];
	}
	pv = f(ym, ye, xm, xe, Q);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(!V[i][j]) continue;
		pii mid = f(L, i, j, xm-xs, ye-ym+xe-xs);
		//pii mid = f(L, i, j, ye-ym+xm-xs, L-1);
		pii fin = pii(i, j) - mid + pv[mid.first][mid.second];
		W[fin.first][fin.second] += V[i][j];
		ret1[i][j] = fin;
	}
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
		if(ret[i][j].first < 0) continue;
		ret[i][j] = ret1[ret[i][j].first][ret[i][j].second];
	}

	/*printf("RET F %d %d %d %d\n", ys, ye, xs, xe);
	for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++)
		printf("%d %d : %d %d\n", i, j, ret[i][j].first, ret[i][j].second);*/
	return ret;
}
int main() {
	scanf("%d%d", &N, &Q);
	for(int i = 0; i < N; i++) fill(d[i], d[i]+N, 1);
	for(int i = 1; i < N; i++) for(int j = 1; j < N; j++) scanf(" %s", str[i][j]);
	for(int i = 0; i < Q; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
	{
		const int L = 2*N-1;
		Mat V(L+1, vector<int>(L+1, 0));
		for(int i = 0; i < Q; i++) V[A[i]][B[i]]++;
		Mati ret = f(0, N-1, 0, N-1, V);
		vector<int> tmp(L, 0);
		for(int i = 0; i <= L; i++) for(int j = 0; j <= L; j++) {
			if(!V[i][j]) continue;
			pii cnt = ret[i][j];
			for(int k = 0; k < cnt.first; k++) tmp[k] = 0;
			for(int k = cnt.first; k < cnt.first+cnt.second; k++) tmp[k] = 1;
			for(int k = cnt.first+cnt.second; k < L; k++) tmp[k] = 2;
			for(int x = 0; x < N; x++) d[N-1][x] += tmp[x] * V[i][j];
			for(int y = N-2; 0 <= y; y--) d[y][N-1] += tmp[2*N-2 - y] * V[i][j];
		}
	}
	for(int i = 0; i < N; puts(""), i++) for(int j = 0; j < N; j++) printf("%d ", d[i][j]);
	return 0;
}

Compilation message

queen.cpp: In function 'int main()':
queen.cpp:217:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  217 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
queen.cpp:219:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  219 |  for(int i = 1; i < N; i++) for(int j = 1; j < N; j++) scanf(" %s", str[i][j]);
      |                                                        ~~~~~^~~~~~~~~~~~~~~~~~
queen.cpp:220:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  220 |  for(int i = 0; i < Q; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 24 ms 3308 KB Output is correct
4 Correct 25 ms 3308 KB Output is correct
5 Correct 234 ms 21996 KB Output is correct
6 Correct 250 ms 21996 KB Output is correct
7 Correct 231 ms 22124 KB Output is correct
8 Correct 707 ms 57196 KB Output is correct
9 Correct 691 ms 57216 KB Output is correct
10 Correct 1304 ms 106732 KB Output is correct
11 Correct 1314 ms 106780 KB Output is correct
12 Correct 1303 ms 106860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 257 ms 22508 KB Output is correct
3 Correct 455 ms 38380 KB Output is correct
4 Correct 1392 ms 106988 KB Output is correct
5 Correct 1412 ms 107116 KB Output is correct
6 Correct 1396 ms 107116 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 37 ms 3564 KB Output is correct
3 Correct 808 ms 57452 KB Output is correct
4 Correct 1507 ms 107124 KB Output is correct
5 Correct 1478 ms 107148 KB Output is correct
6 Correct 1479 ms 107040 KB Output is correct
7 Correct 1557 ms 107152 KB Output is correct
8 Correct 1626 ms 107096 KB Output is correct
9 Correct 1581 ms 106992 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1514 ms 80532 KB Output is correct
2 Correct 1731 ms 80396 KB Output is correct
3 Correct 4591 ms 131116 KB Output is correct
4 Correct 3320 ms 130944 KB Output is correct
5 Correct 3270 ms 130960 KB Output is correct
6 Correct 3328 ms 130900 KB Output is correct
7 Correct 3327 ms 131040 KB Output is correct
8 Correct 4132 ms 131344 KB Output is correct
9 Correct 4245 ms 131000 KB Output is correct
10 Correct 3430 ms 131024 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 247 ms 18028 KB Output is correct
6 Correct 247 ms 18028 KB Output is correct
7 Correct 244 ms 17976 KB Output is correct
8 Correct 243 ms 18028 KB Output is correct
9 Correct 3668 ms 133096 KB Output is correct
10 Correct 4555 ms 133488 KB Output is correct
11 Correct 3710 ms 133740 KB Output is correct
12 Correct 3298 ms 133452 KB Output is correct
13 Correct 3323 ms 133428 KB Output is correct
14 Correct 3670 ms 131100 KB Output is correct
15 Correct 4570 ms 131092 KB Output is correct
16 Correct 3685 ms 131572 KB Output is correct
17 Correct 3325 ms 131164 KB Output is correct
18 Correct 3323 ms 130964 KB Output is correct