| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 201166 |
2020-02-09T13:57:19 Z |
dennisstar |
여왕벌 (KOI15_queen) |
C++17 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
