Submission #348354

#	Time	Username	Problem	Language	Result	Execution time	Memory
348354		koioi.org-youngyojun	여왕벌 (KOI15_queen)	C++17	101 / 100	4591 ms	133740 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32
• Subtask 5: 1 / 1