oj.uz

Submission #38590

# Submission time Handle Problem Language Result Execution time Memory
38590 2018-01-04T23:39:24 Z kajebiii 여왕벌 (KOI15_queen) C++14
101 / 100
 2173 ms 42604 KB 
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 777;

int N, Q, Ans[MAX_N][MAX_N];
char F[MAX_N][MAX_N][30];
int choose(int x, int y, int l, int d, int u) {
	char f = F[x][y][l*9+d*3+u];
	return (f == 'L' ? l : (f == 'D' ? d : u));
}
int cut(int v, int minV, int maxV) {
	return min(max(v, minV), maxV);
}
void getAns(int xa, int xb, int ya, int yb, vector<int> &in, vector<int> &ch);
void change(int xa, int xb, int ya, int yb, vector<int> &pin, vector<int> &pch, int ps, int st) {
	int n = xb - xa, m = yb - ya, s = n + m + 2;
	vector<int> in(s*s, 0), ch(s*s, 0);
	for(int i=0; i<ps; i++) for(int j=i; j<ps; j++) if(pin[i*ps+j]) {
		int pc = pch[i*ps+j], pci = pc/ps, pcj = pc%ps;
		int ni = cut(pci-st, 0, s-1), nj = cut(pcj-st, 0, s-1);
		in[ni*s + nj] += pin[i*ps+j];
		//printf("plus [%d %d] + %d(%d %d)\n", ni, nj, pin[i*ps+j], i, j);
	}
	getAns(xa, xb, ya, yb, in, ch);
	for(int i=0; i<ps; i++) for(int j=i; j<ps; j++) if(pin[i*ps+j]) {
		int pc = pch[i*ps+j], pci = pc/ps, pcj = pc%ps;
		int ni = cut(pci-st, 0, s-1), nj = cut(pcj-st, 0, s-1);
		int c = ch[ni*s + nj], ci = c/s, cj = c%s;
		int npci = pci - ni + ci, npcj = pcj - nj + cj;
		pch[i*ps+j] = npci*ps + npcj;
		//printf("[%d %d] => [%d %d]\n", pci, pcj, npci, npcj);
	}
}
void getAns(int xa, int xb, int ya, int yb, vector<int> &in, vector<int> &ch) {
	int n = xb - xa, m = yb - ya, s = n + m + 2;
	for(int i=0; i<s; i++) for(int j=i; j<s; j++) ch[i*s+j] = i*s+j;
	//printf("%d %d | %d %d :\n", xa, xb, ya, yb);
	//for(int i=0; i<s; i++) for(int j=i; j<s; j++) if(in[i*s+j]) printf("%d %d : %d\n", i, j, in[i*s+j]);
	if(n == 0 || m == 0) return;
	if(n == 1 && m == 1) {
		int val[3];
		for(int i=0; i<s; i++) for(int j=i; j<s; j++) if(in[i*s+j]) {
			for(int k=0; k<3; k++) val[k] = (k<i ? 0 : (k<j ? 1 : 2));
			Ans[xa][ya] += in[i*s+j] * val[1];

			val[1] = choose(xb, yb, val[0], val[1], val[2]);
			int cnt[2] = {0, 0};
			for(int k=0; k<3; k++) if(val[k] < 2) cnt[val[k]]++;
			cnt[1] += cnt[0];
			ch[i*s+j] = cnt[0]*s + cnt[1];
		}
		return;
	}
	int xm = (xa + xb) >> 1, ym = (ya + yb) >> 1;
	change(xa, xm, ya, ym, in, ch, s, xb-xm);
	change(xa, xm, ym, yb, in, ch, s, xb-xm+ym-ya);
	change(xm, xb, ya, ym, in, ch, s, 0);
	change(xm, xb, ym, yb, in, ch, s, ym-ya);
}
int main() {
	cin >> N >> Q;
	for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) {
		if(i < N && j < N) scanf("%s", F[i][j]);
		else for(int k=0; k<27; k++) F[i][j][k] = 'U';
	}
	int s = 2*N+2;
	vector<int> in(s*s, 0), ch(s*s, 0);
	while(Q--) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		x++; y+=x;
		in[x*s+y]++;
	}
	getAns(0, N, 0, N, in, ch);
	for(int i=0; i<N; i++, puts("")) for(int j=0; j<N; j++) printf("%d ", Ans[i][j]+1);
	return 0;
}

Compilation message

queen.cpp: In function 'int main()':
queen.cpp:74:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(i < N && j < N) scanf("%s", F[i][j]);
                                          ^
queen.cpp:80:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22064 KB Output is correct
2 Correct 0 ms 22064 KB Output is correct
3 Correct 6 ms 22540 KB Output is correct
4 Correct 9 ms 22540 KB Output is correct
5 Correct 119 ms 25916 KB Output is correct
6 Correct 109 ms 25916 KB Output is correct
7 Correct 103 ms 25916 KB Output is correct
8 Correct 243 ms 32612 KB Output is correct
9 Correct 203 ms 32612 KB Output is correct
10 Correct 506 ms 42604 KB Output is correct
11 Correct 513 ms 42604 KB Output is correct
12 Correct 586 ms 42604 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22064 KB Output is correct
2 Correct 113 ms 25916 KB Output is correct
3 Correct 213 ms 28836 KB Output is correct
4 Correct 599 ms 42604 KB Output is correct
5 Correct 626 ms 42604 KB Output is correct
6 Correct 606 ms 42604 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22064 KB Output is correct
2 Correct 19 ms 22540 KB Output is correct
3 Correct 299 ms 32612 KB Output is correct
4 Correct 743 ms 42604 KB Output is correct
5 Correct 726 ms 42604 KB Output is correct
6 Correct 729 ms 42604 KB Output is correct
7 Correct 799 ms 42604 KB Output is correct
8 Correct 819 ms 42604 KB Output is correct
9 Correct 696 ms 42604 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 32612 KB Output is correct
2 Correct 763 ms 32612 KB Output is correct
3 Correct 1869 ms 42604 KB Output is correct
4 Correct 1293 ms 42604 KB Output is correct
5 Correct 1226 ms 42604 KB Output is correct
6 Correct 1263 ms 42604 KB Output is correct
7 Correct 1226 ms 42604 KB Output is correct
8 Correct 1059 ms 42604 KB Output is correct
9 Correct 1126 ms 42604 KB Output is correct
10 Correct 1423 ms 42604 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22064 KB Output is correct
2 Correct 0 ms 22064 KB Output is correct
3 Correct 0 ms 22064 KB Output is correct
4 Correct 0 ms 22064 KB Output is correct
5 Correct 266 ms 22064 KB Output is correct
6 Correct 293 ms 22064 KB Output is correct
7 Correct 293 ms 22064 KB Output is correct
8 Correct 309 ms 22064 KB Output is correct
9 Correct 1559 ms 42528 KB Output is correct
10 Correct 2173 ms 42528 KB Output is correct
11 Correct 1569 ms 42528 KB Output is correct
12 Correct 1363 ms 42528 KB Output is correct
13 Correct 1396 ms 42528 KB Output is correct
14 Correct 1513 ms 42604 KB Output is correct
15 Correct 1973 ms 42604 KB Output is correct
16 Correct 1453 ms 42604 KB Output is correct
17 Correct 1206 ms 42604 KB Output is correct
18 Correct 1323 ms 42604 KB Output is correct