oj.uz

Submission #200171

# Submission time Handle Problem Language Result Execution time Memory
200171 2020-02-05T15:36:10 Z gs14004 여왕벌 (KOI15_queen) C++17
101 / 100
 2630 ms 103600 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 <= 5 || ey - sy <= 5){
		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 376 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 36 ms 5496 KB Output is correct
6 Correct 38 ms 5496 KB Output is correct
7 Correct 35 ms 5496 KB Output is correct
8 Correct 90 ms 11768 KB Output is correct
9 Correct 87 ms 11900 KB Output is correct
10 Correct 167 ms 18168 KB Output is correct
11 Correct 165 ms 18168 KB Output is correct
12 Correct 167 ms 18296 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 46 ms 8536 KB Output is correct
3 Correct 83 ms 16856 KB Output is correct
4 Correct 206 ms 36312 KB Output is correct
5 Correct 205 ms 36312 KB Output is correct
6 Correct 211 ms 36308 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 16 ms 2948 KB Output is correct
3 Correct 140 ms 23812 KB Output is correct
4 Correct 244 ms 37052 KB Output is correct
5 Correct 237 ms 36792 KB Output is correct
6 Correct 241 ms 37052 KB Output is correct
7 Correct 242 ms 36796 KB Output is correct
8 Correct 261 ms 36916 KB Output is correct
9 Correct 319 ms 36792 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 49636 KB Output is correct
2 Correct 667 ms 64960 KB Output is correct
3 Correct 2630 ms 80664 KB Output is correct
4 Correct 2520 ms 80788 KB Output is correct
5 Correct 775 ms 80728 KB Output is correct
6 Correct 760 ms 80588 KB Output is correct
7 Correct 793 ms 80464 KB Output is correct
8 Correct 836 ms 102220 KB Output is correct
9 Correct 953 ms 102140 KB Output is correct
10 Correct 886 ms 80288 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 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 257 ms 27896 KB Output is correct
6 Correct 276 ms 27856 KB Output is correct
7 Correct 253 ms 27896 KB Output is correct
8 Correct 260 ms 28000 KB Output is correct
9 Correct 964 ms 78516 KB Output is correct
10 Correct 1574 ms 80076 KB Output is correct
11 Correct 954 ms 80072 KB Output is correct
12 Correct 758 ms 79688 KB Output is correct
13 Correct 759 ms 100856 KB Output is correct
14 Correct 970 ms 103520 KB Output is correct
15 Correct 1513 ms 103572 KB Output is correct
16 Correct 1020 ms 103484 KB Output is correct
17 Correct 780 ms 103600 KB Output is correct
18 Correct 801 ms 103392 KB Output is correct