Submission #200162

#	Time	Username	Problem	Language	Result	Execution time	Memory
200162		gs14004	여왕벌 (KOI15_queen)	C++17	10 / 100	5095 ms	213292 KiB

Main

#include<bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 705;

struct kek{
	int a, b, c, cnt;
};

char str[MAXN][MAXN][28];
int n, a[MAXN][MAXN];

vector<pi> get_border(int sx, int ex, int sy, int ey){
	vector<pi> v;
	for(int i=ex; i>=sx; i--) v.emplace_back(i, sy);
	for(int i=sy+1; i<=ey; i++) v.emplace_back(sx, i);
	return v;
}

int aux[4][4];

kek splice(kek i, int l, int r){
	auto reduce = [&](int &x, int &y){
		int minv = min(x, y);
		x -= minv; y -= minv;
	};
	int nl = l, nr = i.a + i.b + i.c - r - 1;
	reduce(nl, i.a); reduce(nl, i.b); reduce(nl, i.c);
	reduce(nr, i.c); reduce(nr, i.b); reduce(nr, i.a); 
	return i;
}

kek merge(kek l, kek r, int x, int y){
	auto m = splice(l, x, y);
	kek new_k = {l.a + r.a - m.a, l.b + r.b - m.b, l.c + r.c - m.c, l.cnt};
	return new_k;
}

void solve(int sx, int ex, int sy, int ey, vector<kek> &v){
	if(ex - sx <= 1 || ey - sy <= 1){
		auto B = get_border(0, ex - sx, 0, ey - sy);
		for(auto &i : v){
			memset(aux, 0, sizeof(aux));
			for(int j=i.a; j<i.a + i.b; j++){
				aux[B[j].first][B[j].second] = 1;
			}
			for(int j=i.a+i.b; j<sz(B); j++){
				aux[B[j].first][B[j].second] = 2;
			}
			int cc = i.cnt;
			for(int i=1; i<=ex-sx; i++){
				for(int j=1; j<=ey-sy; j++){
					int val = aux[i-1][j] + aux[i-1][j-1] * 3 + aux[i][j-1] * 9;
					char choice = str[i + sx][j + sy][val];
					if(choice == 'L') aux[i][j] = aux[i][j-1];
					if(choice == 'D') aux[i][j] = aux[i-1][j-1];
					if(choice == 'U') aux[i][j] = aux[i-1][j];
					a[sx + i][sy + j] += aux[i][j] * cc;
				}
			}
			int c[3] = {};
			for(int i=sy; i<=ey; i++) c[aux[ex-sx][i-sy]]++;
			for(int i=sx; i<ex; i++) c[aux[i-sx][ey-sy]]++;
			i.a = c[0];
			i.b = c[1];
			i.c = c[2];
		}
		return;
	}
	int mx = (sx + ex) / 2;
	int my = (sy + ey) / 2;
	int vec[5] = {0, ex - mx, my - sy + ex - mx, my - sy + ex - sx, ey - sy + ex - sx};
	vector<kek> split(sz(v));
	for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[1], vec[3]);
	solve(sx, mx, sy, my, split);
	for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[1], vec[3]);
	for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[2], vec[4]);
	solve(sx, mx, my, ey, split);
	for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[2], vec[4]);
	for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[0], vec[2]);
	solve(mx, ex, sy, my, split);
	for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[0], vec[2]);
	vec[1] = my - sy;
	vec[3] = vec[4] - (mx - sx);
	for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[1], vec[3]);
	solve(mx, ex, my, ey, split);
	for(int i=0; i<sz(v); i++) v[i] = merge(v[i], split[i], vec[1], vec[3]);
}

int main(){
	int dx[2 * MAXN] = {};
	int q;
	scanf("%d %d",&n,&q);
	for(int i=1; i<n; i++){
		for(int j=1; j<n; j++){
			scanf("%s", str[i][j]);
		}
	}
	vector<kek> v(q);
	for(auto &i : v){
		scanf("%d %d %d",&i.a,&i.b,&i.c);
		i.cnt = 1;
		dx[i.a] += 1;
		dx[i.a + i.b] += 1;
	}
	for(int i=1; i<=2*n+2; i++) dx[i] += dx[i-1];
	auto vect = get_border(0, n-1, 0, n-1);
	for(int i=0; i<sz(vect); i++) a[vect[i].first][vect[i].second] += dx[i];
	memset(dx, 0, sizeof(dx));
	solve(0, n - 1, 0, n - 1, v);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			printf("%d ", a[i][j] + 1);
		}
		puts("");
	}
}

Compilation message (stderr)

queen.cpp: In function 'int main()':
queen.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
queen.cpp:99:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", str[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~
queen.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&i.a,&i.b,&i.c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 34
• Subtask 4: 0 / 32
• Subtask 5: 0 / 1