oj.uz

답안 #201166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201166 2020-02-09T13:57:19 Z dennisstar 여왕벌 (KOI15_queen) C++17
101 / 100
 3549 ms 112992 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define Enc(x, y) (H2[x][y])
#define Dec(x) (H1[x])
#define getcnt(x) ((x+2)*(x+1)/2)
using namespace std;
typedef vector<int> vim;
typedef pair<int, int> pii;

int M, N;
int c[710][710][3][3][3];
int ans[710][710];

int Fen[1410];
void upd(int t, int v) { while (t<=M*2+1) Fen[t]+=v, t+=t&-t; }
int get(int t) { int ret=0; while (t) ret+=Fen[t], t-=t&-t; return ret; }

vector<pii> H1; int H2[1410][1410];
void init() {
	for (int i=0; i<=2*M-1; i++) for (int j=0; j<=2*M-1-i; j++) H1.eb(i, j);
	sort(all(H1), [](pii p1, pii p2){ return p1.fi+p1.se<p2.fi+p2.se; });
	for (int i=0; i<H1.size(); i++) H2[H1[i].fi][H1[i].se]=i;
}

pii sum(pii a, pii b) { return pii(a.fi+b.fi, a.se+b.se); }
pii sub(pii a, pii b) { return pii(a.fi-b.fi, a.se-b.se); }

pii cut1(int x, int v) {
	pii P=Dec(x);
	if (P.fi+P.se<=v) return pii(P.fi, P.se);
	if (P.fi<=v) return pii(P.fi, v-P.fi);
	return pii(v, 0);
}

pii cut3(int x, int v, int m) {
	pii P=Dec(x); int c=m-P.fi-P.se;
	if (P.se+c<=v) return pii(v-P.se-c, P.se);
	if (c<=v) return pii(0, v-c);
	return pii(0, 0);
}

vim dnc(vim &A, int x1, int y1, int x2, int y2) {
	int H=(x2-x1+1), W=(y2-y1+1), sz=A.size();
	if (x1==x2&&y1==y2) {
		vim ret(sz); pii im; int x, y, z, w;
		for (int i=0; i<A.size(); i++) {
			im=Dec(i);
			x=((im.fi>=1)?0:(im.fi+im.se>=1)?1:2);
			y=((im.fi>=2)?0:(im.fi+im.se>=2)?1:2);
			z=((im.fi>=3)?0:(im.fi+im.se>=3)?1:2);
			w=c[x1][y1][x][y][z];
			ans[x1][y1]+=A[i]*w;
			ret[i]=(w==0?Enc(1, 0):w==1?Enc(0, 1):Enc(0, 0));
		}
		return ret;
	}
	else if (x1==x2) {
		vim ret(sz), s1, r1, s2, r2; pii im, im1;

		s1.resize(10);
		for (int i=0; i<A.size(); i++) {
			im=cut1(i, 3);
			s1[Enc(im.fi, im.se)]+=A[i];
		}
		r1=dnc(s1, x1, y1, x1, y1);

		s2.resize(10);
		for (int i=0; i<A.size(); i++) {
			im=cut1(i, 3);
			im=sum(Dec(r1[Enc(im.fi, im.se)]), cut3(i, 2, H+W+1));
			s2[Enc(im.fi, im.se)]+=A[i];
		}
		r2=dnc(s2, x2, y2, x2, y2);

		for (int i=0; i<A.size(); i++) {
			im=cut1(i, 3); im1=sum(Dec(r1[Enc(im.fi, im.se)]), cut3(i, 2, H+W+1));
			im=sum(Dec(r1[Enc(im.fi, im.se)]), Dec(r2[Enc(im1.fi, im1.se)]));
			ret[i]=Enc(im.fi, im.se);
		}
		return ret;
	}
	else if (y1==y2) {
		vim ret(sz), s1, r1, s2, r2; pii im, im1;

		s1.resize(10);
		for (int i=0; i<A.size(); i++) {
			im=cut3(i, 3, H+W+1);
			s1[Enc(im.fi, im.se)]+=A[i];
		}
		r1=dnc(s1, x1, y1, x1, y1);

		s2.resize(10);
		for (int i=0; i<A.size(); i++) {
			im=cut3(i, 3, H+W+1);
			im=sum(Dec(r1[Enc(im.fi, im.se)]), cut1(i, 2));
			s2[Enc(im.fi, im.se)]+=A[i];
		}
		r2=dnc(s2, x2, y2, x2, y2);

		for (int i=0; i<A.size(); i++) {
			im=cut3(i, 3, H+W+1); im1=sum(Dec(r1[Enc(im.fi, im.se)]), cut1(i, 2));
			im=sum(Dec(r1[Enc(im.fi, im.se)]), Dec(r2[Enc(im1.fi, im1.se)]));
			ret[i]=Enc(im.fi, im.se);
		}
		return ret;
	}

	vim s1, r1, s2, r2, s3, r3, s4, r4, ret(A.size());
	pii im; int h, w;
	int mdx=(x1+x2)/2, mdy=(y1+y2)/2;
	

	h=mdx-x1+1, w=mdy-y1+1;
	s1.resize(getcnt(h+w+1));
	for (int i=0; i<A.size(); i++) {
		im=Dec(i);
		im=sub(sub(im, cut1(i, H-h)), cut3(i, W-w, H+W+1));
		s1[Enc(im.fi, im.se)]+=A[i];
	}
	r1=dnc(s1, x1, y1, mdx, mdy);
	
	for (int i=0; i<A.size(); i++) {
		im=Dec(i);
		im=sub(sub(im, cut1(i, H-h)), cut3(i, W-w, H+W+1));
		im=sum(sum(cut1(i, H-h+1), Dec(r1[Enc(im.fi, im.se)])), cut3(i, W-w+1, H+W+1));
		ret[i]=Enc(im.fi, im.se);
	}


	h=x2-mdx, w=mdy-y1+1;
	s2.resize(getcnt(h+w+1));
	for (int i=0; i<A.size(); i++) {
		im=cut1(ret[i], h+w+1);
		s2[Enc(im.fi, im.se)]+=A[i];
	}
	r2=dnc(s2, mdx+1, y1, x2, mdy);
	
	for (int i=0; i<A.size(); i++) {
		im=cut1(ret[i], h+w+1);
		im=sum(sum(cut1(ret[i], 1), Dec(r2[Enc(im.fi, im.se)])), cut3(ret[i], H+W+1-h-w, H+W+1));
		ret[i]=Enc(im.fi, im.se);
	}


	h=mdx-x1+1, w=y2-mdy;
	s3.resize(getcnt(h+w+1));
	for (int i=0; i<A.size(); i++) {
		im=cut3(ret[i], h+w+1, H+W+1);
		s3[Enc(im.fi, im.se)]+=A[i];
	}
	r3=dnc(s3, x1, mdy+1, mdx, y2);

	for (int i=0; i<A.size(); i++) {
		im=cut3(ret[i], h+w+1, H+W+1);
		im=sum(cut1(ret[i], H+W+1-h-w), sum(Dec(r3[Enc(im.fi, im.se)]), cut3(ret[i], 1, H+W+1)));
		ret[i]=Enc(im.fi, im.se);
	}


	h=x2-mdx, w=y2-mdy;
	s4.resize(getcnt(h+w+1));
	for (int i=0; i<A.size(); i++) {
		im=sub(sub(Dec(ret[i]), cut1(ret[i], W-w)), cut3(ret[i], H-h, H+W+1));
		s4[Enc(im.fi, im.se)]+=A[i];
	}
	r4=dnc(s4, mdx+1, mdy+1, x2, y2);

	for (int i=0; i<A.size(); i++) {
		im=sub(sub(Dec(ret[i]), cut1(ret[i], W-w)), cut3(ret[i], H-h, H+W+1));
		im=sum(cut1(ret[i], W-w+1), sum(Dec(r4[Enc(im.fi, im.se)]), cut3(ret[i], H-h+1, H+W+1)));
		ret[i]=Enc(im.fi, im.se);
	}

	for (auto &i:ret) {
		im=sub(sub(Dec(i), cut1(i, 1)), cut3(i, 1, H+W+1));
		i=Enc(im.fi, im.se);
	}

	return ret;
}

int main() {
	scanf("%d %d", &M, &N); init();
	char C;
	for (int i=1; i<M; i++) for (int j=1; j<M; j++) for (int x=0; x<3; x++) for (int y=0; y<3; y++) for (int z=0; z<3; z++) {
		scanf(" %c", &C);
		if (C=='L') c[i][j][x][y][z]=x;
		else if (C=='D') c[i][j][x][y][z]=y;
		else c[i][j][x][y][z]=z;
	}
	//3H(2*M-1) = (2M+1)C2
	vim A(getcnt(M*2-1));
	for (int i=1; i<=N; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		A[Enc(u, v)]++;
		upd(u+1, 1); upd(u+v+1, 1);
	}
	dnc(A, 1, 1, M-1, M-1);
	int t=1;
	for (int i=M-1; i>=0; i--, t++) ans[i][0]=get(t);
	for (int i=1; i<M; i++, t++) ans[0][i]=get(t);

	for (int i=0; i<M; i++) {
		for (int j=0; j<M; j++) printf("%d ", ans[i][j]+1);
		puts("");
	}
	return 0;
}

Compilation message

queen.cpp: In function 'void init()':
queen.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<H1.size(); i++) H2[H1[i].fi][H1[i].se]=i;
                ~^~~~~~~~~~
queen.cpp: In function 'vim dnc(vim&, int, int, int, int)':
queen.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<A.size(); i++) {
                 ~^~~~~~~~~
queen.cpp:118:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:125:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:135:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:141:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:150:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:156:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:165:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp:171:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<A.size(); i++) {
                ~^~~~~~~~~
queen.cpp: In function 'int main()':
queen.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N); init();
  ~~~~~^~~~~~~~~~~~~~~~~
queen.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &C);
   ~~~~~^~~~~~~~~~~
queen.cpp:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 54 ms 3804 KB Output is correct
4 Correct 53 ms 3700 KB Output is correct
5 Correct 481 ms 22096 KB Output is correct
6 Correct 469 ms 22116 KB Output is correct
7 Correct 467 ms 22116 KB Output is correct
8 Correct 1334 ms 52316 KB Output is correct
9 Correct 1283 ms 52316 KB Output is correct
10 Correct 2653 ms 91980 KB Output is correct
11 Correct 2786 ms 91988 KB Output is correct
12 Correct 2739 ms 91816 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 504 KB Output is correct
2 Correct 472 ms 22116 KB Output is correct
3 Correct 852 ms 36444 KB Output is correct
4 Correct 2722 ms 91984 KB Output is correct
5 Correct 2650 ms 91856 KB Output is correct
6 Correct 2753 ms 91832 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 54 ms 3828 KB Output is correct
3 Correct 1359 ms 55516 KB Output is correct
4 Correct 2751 ms 101464 KB Output is correct
5 Correct 2726 ms 101588 KB Output is correct
6 Correct 2796 ms 101540 KB Output is correct
7 Correct 2754 ms 101328 KB Output is correct
8 Correct 2621 ms 101584 KB Output is correct
9 Correct 2651 ms 101320 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1731 ms 58024 KB Output is correct
2 Correct 1632 ms 66396 KB Output is correct
3 Correct 3180 ms 112884 KB Output is correct
4 Correct 3509 ms 112852 KB Output is correct
5 Correct 3366 ms 112828 KB Output is correct
6 Correct 3348 ms 112808 KB Output is correct
7 Correct 3264 ms 112728 KB Output is correct
8 Correct 3159 ms 112992 KB Output is correct
9 Correct 3105 ms 112856 KB Output is correct
10 Correct 3249 ms 112908 KB Output is correct

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 380 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 305 ms 6264 KB Output is correct
6 Correct 295 ms 6264 KB Output is correct
7 Correct 303 ms 6264 KB Output is correct
8 Correct 304 ms 6264 KB Output is correct
9 Correct 3348 ms 90664 KB Output is correct
10 Correct 3332 ms 112652 KB Output is correct
11 Correct 3008 ms 112568 KB Output is correct
12 Correct 3549 ms 112672 KB Output is correct
13 Correct 3311 ms 112660 KB Output is correct
14 Correct 3250 ms 112772 KB Output is correct
15 Correct 3220 ms 112904 KB Output is correct
16 Correct 2927 ms 112872 KB Output is correct
17 Correct 3315 ms 112816 KB Output is correct
18 Correct 3339 ms 112648 KB Output is correct