oj.uz

Submission #200176

# Submission time Handle Problem Language Result Execution time Memory
200176 2020-02-05T15:37:55 Z gs14004 여왕벌 (KOI15_queen) C++17
101 / 100
 1666 ms 100756 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 <= 3 || ey - sy <= 3){
		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 6 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 43 ms 5548 KB Output is correct
6 Correct 39 ms 5496 KB Output is correct
7 Correct 57 ms 5496 KB Output is correct
8 Correct 112 ms 11768 KB Output is correct
9 Correct 107 ms 11988 KB Output is correct
10 Correct 186 ms 18168 KB Output is correct
11 Correct 184 ms 18180 KB Output is correct
12 Correct 198 ms 18296 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 888 KB Output is correct
2 Correct 53 ms 8464 KB Output is correct
3 Correct 84 ms 12884 KB Output is correct
4 Correct 256 ms 26576 KB Output is correct
5 Correct 242 ms 26560 KB Output is correct
6 Correct 235 ms 26560 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 888 KB Output is correct
2 Correct 21 ms 2948 KB Output is correct
3 Correct 167 ms 17436 KB Output is correct
4 Correct 288 ms 27352 KB Output is correct
5 Correct 261 ms 27136 KB Output is correct
6 Correct 274 ms 27168 KB Output is correct
7 Correct 268 ms 27064 KB Output is correct
8 Correct 308 ms 27372 KB Output is correct
9 Correct 350 ms 27064 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 49636 KB Output is correct
2 Correct 698 ms 49568 KB Output is correct
3 Correct 1666 ms 78780 KB Output is correct
4 Correct 759 ms 78936 KB Output is correct
5 Correct 814 ms 78920 KB Output is correct
6 Correct 763 ms 78804 KB Output is correct
7 Correct 810 ms 78732 KB Output is correct
8 Correct 832 ms 100756 KB Output is correct
9 Correct 982 ms 100252 KB Output is correct
10 Correct 882 ms 78536 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 263 ms 27856 KB Output is correct
6 Correct 256 ms 27768 KB Output is correct
7 Correct 264 ms 27772 KB Output is correct
8 Correct 255 ms 27728 KB Output is correct
9 Correct 1138 ms 78476 KB Output is correct
10 Correct 1641 ms 78444 KB Output is correct
11 Correct 1060 ms 78664 KB Output is correct
12 Correct 799 ms 78668 KB Output is correct
13 Correct 809 ms 78624 KB Output is correct
14 Correct 1034 ms 78664 KB Output is correct
15 Correct 1642 ms 78624 KB Output is correct
16 Correct 1039 ms 78668 KB Output is correct
17 Correct 842 ms 78628 KB Output is correct
18 Correct 839 ms 78648 KB Output is correct