oj.uz

Submission #200162

# Submission time Handle Problem Language Result Execution time Memory
200162 2020-02-05T14:45:18 Z gs14004 여왕벌 (KOI15_queen) C++17
10 / 100
 5000 ms 213292 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 10 ms 1528 KB Output is correct
5 Correct 48 ms 7416 KB Output is correct
6 Correct 46 ms 7416 KB Output is correct
7 Correct 55 ms 7416 KB Output is correct
8 Correct 130 ms 17912 KB Output is correct
9 Correct 133 ms 17912 KB Output is correct
10 Correct 230 ms 30200 KB Output is correct
11 Correct 228 ms 30200 KB Output is correct
12 Correct 226 ms 30200 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1220 KB Output is correct
2 Execution timed out 5095 ms 9588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1224 KB Output is correct
2 Execution timed out 5021 ms 3532 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 185444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 320 ms 21880 KB Output is correct
6 Correct 331 ms 22008 KB Output is correct
7 Correct 534 ms 37624 KB Output is correct
8 Correct 542 ms 37640 KB Output is correct
9 Execution timed out 5015 ms 213292 KB Time limit exceeded
10 Halted 0 ms 0 KB -