제출 #38590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38590		kajebiii	여왕벌 (KOI15_queen)	C++14	101 / 100	2173 ms	42604 KiB

Main

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32
• Subtask 5: 1 / 1