oj.uz

Submission #200174

# Submission time Handle Problem Language Result Execution time Memory
200174 2020-02-05T15:37:37 Z gs14004 여왕벌 (KOI15_queen) C++17
101 / 100
 1647 ms 102916 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, ra, rb, rc;
	kek(){}
	kek(int a, int b, int c, int cnt): a(a), b(b), c(c), cnt(cnt), ra(a), rb(b), rc(c) {}
};

int aux[2 * MAXN][2 * MAXN];

vector<kek> compress(vector<kek> &v){
	for(auto &i : v){
		aux[i.a][i.b] += i.cnt;
	}
	vector<kek> w;
	for(auto &i : v){
		if(aux[i.a][i.b]){
			w.emplace_back(i.a, i.b, i.c, aux[i.a][i.b]);
			aux[i.a][i.b] = 0;
		}
	}
	return w;
}

void write(vector<kek> &write_pos, vector<kek> &v, vector<kek> &w){
	int tot = w[0].a + w[0].b + w[0].c;
	for(auto &i : w) aux[i.a][i.b] = (i.ra << 12) + i.rb;
	for(int itr = 0; itr < sz(write_pos); itr++){
		auto i = v[itr];
		int nxta = (aux[i.a][i.b] >> 12);
		int nxtb = (aux[i.a][i.b] & 4095);
		int nxtc = tot - nxta - nxtb;
		write_pos[itr].ra += nxta - i.a;
		write_pos[itr].rb += nxtb - i.b;
		write_pos[itr].rc += nxtc - i.c;
	}
	for(auto &i : w) aux[i.a][i.b] = 0;
}

char str[MAXN][MAXN][30];
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;
}

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.ra + i.rb + i.rc - r - 1;
	reduce(nl, i.ra); reduce(nl, i.rb); reduce(nl, i.rc);
	reduce(nr, i.rc); reduce(nr, i.rb); reduce(nr, i.ra); 
	return kek(i.ra, i.rb, i.rc, i.cnt);
}

void solve(int sx, int ex, int sy, int ey, vector<kek> &v){
	if(ex - sx <= 4 || ey - sy <= 4){
		auto B = get_border(0, ex - sx, 0, ey - sy);
		for(auto &i : v){
			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.ra = c[0];
			i.rb = c[1];
			i.rc = c[2]; 
			for(int i=0; i<=ex-sx; i++){
				for(int j=0; j<=ey-sy; j++){
					aux[i][j] = 0;
				}
			}
		}
		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]);
		vector<kek> comp = compress(split);
		solve(sx, mx, sy, my, comp);
		write(v, split, comp);
	}
	{
		for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[2], vec[4]);
		vector<kek> comp = compress(split);
		solve(sx, mx, my, ey, comp);
		write(v, split, comp);
	}
	{
		for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[0], vec[2]);
		vector<kek> comp = compress(split);
		solve(mx, ex, sy, my, comp);
		write(v, split, comp);
	}
	{
		for(int i=0; i<sz(v); i++) split[i] = splice(v[i], vec[2] - vec[1], vec[2] + vec[4] - vec[3]);
		vector<kek> comp = compress(split);
		solve(mx, ex, my, ey, comp);
		write(v, split, comp);
	}
}

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;
	}
	v = compress(v);
	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];
	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:135: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:138: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:143: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 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 9 ms 1528 KB Output is correct
4 Correct 9 ms 1528 KB Output is correct
5 Correct 38 ms 5496 KB Output is correct
6 Correct 37 ms 5496 KB Output is correct
7 Correct 38 ms 5496 KB Output is correct
8 Correct 90 ms 11844 KB Output is correct
9 Correct 89 ms 11896 KB Output is correct
10 Correct 174 ms 18168 KB Output is correct
11 Correct 185 ms 18168 KB Output is correct
12 Correct 195 ms 18280 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 51 ms 8536 KB Output is correct
3 Correct 81 ms 16860 KB Output is correct
4 Correct 232 ms 39616 KB Output is correct
5 Correct 229 ms 39512 KB Output is correct
6 Correct 229 ms 39616 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 760 KB Output is correct
2 Correct 20 ms 2948 KB Output is correct
3 Correct 141 ms 23776 KB Output is correct
4 Correct 282 ms 40120 KB Output is correct
5 Correct 269 ms 40116 KB Output is correct
6 Correct 310 ms 40140 KB Output is correct
7 Correct 297 ms 40076 KB Output is correct
8 Correct 325 ms 40124 KB Output is correct
9 Correct 365 ms 40136 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 49636 KB Output is correct
2 Correct 663 ms 67668 KB Output is correct
3 Correct 1604 ms 81372 KB Output is correct
4 Correct 776 ms 81564 KB Output is correct
5 Correct 780 ms 81364 KB Output is correct
6 Correct 833 ms 81392 KB Output is correct
7 Correct 855 ms 81380 KB Output is correct
8 Correct 1647 ms 102916 KB Output is correct
9 Correct 1036 ms 102884 KB Output is correct
10 Correct 935 ms 80968 KB Output is correct

Subtask #5
1.0 / 1.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 6 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 303 ms 27896 KB Output is correct
6 Correct 282 ms 27872 KB Output is correct
7 Correct 264 ms 27896 KB Output is correct
8 Correct 276 ms 27924 KB Output is correct
9 Correct 1084 ms 78692 KB Output is correct
10 Correct 1631 ms 80724 KB Output is correct
11 Correct 1038 ms 80624 KB Output is correct
12 Correct 769 ms 80456 KB Output is correct
13 Correct 774 ms 81700 KB Output is correct
14 Correct 1043 ms 79284 KB Output is correct
15 Correct 1582 ms 79176 KB Output is correct
16 Correct 1049 ms 79152 KB Output is correct
17 Correct 821 ms 79144 KB Output is correct
18 Correct 816 ms 79096 KB Output is correct