| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27182 |
2017-07-10T02:20:24 Z |
검수컵(#1129) |
On the Grid (FXCUP2_grid) |
C++ |
|
1123 ms |
404288 KB |
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int N, Q, row[101010], col[101010]; // A, B, ..., EXQD is actually?
struct itr {
int s, e, key; // this node covers s, e
itr *l, *r;
itr(int s_=0, int e_=0){s=s_, e=e_, key=0, l=NULL, r=NULL;}
} *pl[202020], *mi[202020];
char ra[9], rb[9];
int get_rnum(char *c){
int base = 0, add = 0;
int len = strlen(c);
if(len == 1) base = 1;
if(len == 2) base = 1+26;
if(len == 3) base = 1+26+26*26;
if(len == 4) base = 1+26+26*26+26*26*26;
for(int i=0; i<len; i++) add = add*26 + c[i]-'A';
return base + add;
}
void add_node(itr *me, int y, int v){
while(1){
int ss = me->s, ee = me->e, m = (ss+ee)/2;
me->key += v;
if(ss == ee) break;
if(y <= m){
if(me->l == NULL) me->l = new itr(ss, m);
me = me->l;
}
else{
if(me->r == NULL) me->r = new itr(m+1, ee);
me = me->r;
}
}
}
void find_bound(itr *me, int y, int &left, int &right){
itr *record, *tmp; left=0, right=N+1;
record = NULL, tmp = me;
while(1){ // left
int ss = tmp->s, ee = tmp->e, m = (ss+ee)/2;
if(ss == ee) break;
if(y <= m){
if(tmp->l == NULL){ left=right=y; return; }
tmp = tmp->l;
}
else{
if(tmp->r == NULL){ left=right=y; return; }
if(tmp->l == NULL) left=m, record=NULL;
else if(tmp->l->key != m-ss+1) record = tmp->l;
tmp = tmp->r;
}
}
while(1){
if(record == NULL) break;
int ss = record->s, ee = record->e, m = (ss+ee)/2;
if(ss == ee){ left=ss; break; }
if(record->r == NULL){ left=ee; break; }
if(record->r->key != ee-m) record = record->r;
else record = record->l;
}
record = NULL, tmp = me;
while(1){ // right
int ss = tmp->s, ee = tmp->e, m = (ss+ee)/2;
if(ss == ee) break;
if(y <= m){
if(tmp->r == NULL) right=m+1, record=NULL;
else if(tmp->r->key != ee-m) record = tmp->r;
tmp = tmp->l;
}
else tmp = tmp->r;
}
while(1){
if(record == NULL) break;
int ss = record->s, ee = record->e, m = (ss+ee)/2;
if(ss == ee){ right=ss; break; }
if(record->l == NULL){ right=ss; break; }
if(record->l->key != m-ss+1) record = record->l;
else record = record->r;
}
}
void add_poi(int x, int y, int v){
add_node(pl[x+y-1], y, v);
add_node(mi[x-y+N], y, v);
}
int dist(int x1, int y1, int x2, int y2){
int a=x1-x2, b=y1-y2;
return (a<0?-a:a) + (b<0?-b:b);
}
int main(){
scanf("%d%d", &N, &Q);
for(int i=1; i<2*N; i++) pl[i] = new itr(1, N), mi[i] = new itr(1, N);
for(int i=1; i<=N; i++){
row[i] = col[i] = i;
add_poi(i, i, 1);
}
for(int t=Q; t--;){
int typ, p, q;
scanf("%d", &typ);
if(typ == 1){
scanf(" %s %s", ra, rb); p=get_rnum(ra), q=get_rnum(rb);
add_poi(row[p], col[p], -1); add_poi(row[q], col[q], -1);
swap(row[p], row[q]);
add_poi(row[p], col[p], 1); add_poi(row[q], col[q], 1);
}
if(typ == 2){
scanf("%d%d", &p, &q);
add_poi(row[p], col[p], -1); add_poi(row[q], col[q], -1);
swap(col[p], col[q]);
add_poi(row[p], col[p], 1); add_poi(row[q], col[q], 1);
}
int sx = row[2], sy = col[1], ex = row[1], ey = col[4], xl, xr, yl, yr, dap=999999;
if(sx > ex) swap(sx,ex), swap(sy,ey);
if(sy > ey){
find_bound(mi[row[1]-col[1]+N], col[1], yl, yr);
xl = row[1]-col[1]+yl, xr = row[1]-col[1]+yr;
}
else{
find_bound(pl[row[1]+col[1]-1], col[1], yl, yr);
xl = row[1]+col[1]-yl, xr = row[1]+col[1]-yr;
}
if(xl >= 1 && xl <= N && yl >= 1 && yl <= N) dap = min(dap, dist(sx, sy, xl, yl) + dist(ex, ey, xl, yl));
if(xr >= 1 && xr <= N && yr >= 1 && yr <= N) dap = min(dap, dist(sx, sy, xr, yr) + dist(ex, ey, xr, yr));
printf("%d\n", dap == 999999 ? -1 : dap);
}
return 0;
}
Compilation message
grid.cpp: In function 'int main()':
grid.cpp:100:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
^
grid.cpp:108:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &typ);
^
grid.cpp:110:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s %s", ra, rb); p=get_rnum(ra), q=get_rnum(rb);
^
grid.cpp:116:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &p, &q);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5252 KB |
Output is correct |
| 4 |
Correct |
13 ms |
10136 KB |
Output is correct |
| 5 |
Correct |
23 ms |
14360 KB |
Output is correct |
| 6 |
Correct |
589 ms |
160088 KB |
Output is correct |
| 7 |
Correct |
1053 ms |
404156 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
0 ms |
5252 KB |
Output is correct |
| 10 |
Correct |
9 ms |
10136 KB |
Output is correct |
| 11 |
Correct |
26 ms |
14360 KB |
Output is correct |
| 12 |
Correct |
856 ms |
263312 KB |
Output is correct |
| 13 |
Correct |
1026 ms |
404288 KB |
Output is correct |
| 14 |
Correct |
0 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
0 ms |
5252 KB |
Output is correct |
| 16 |
Correct |
6 ms |
8156 KB |
Output is correct |
| 17 |
Correct |
19 ms |
10664 KB |
Output is correct |
| 18 |
Correct |
569 ms |
152036 KB |
Output is correct |
| 19 |
Correct |
693 ms |
259880 KB |
Output is correct |
| 20 |
Correct |
0 ms |
5120 KB |
Output is correct |
| 21 |
Correct |
0 ms |
5252 KB |
Output is correct |
| 22 |
Correct |
6 ms |
8420 KB |
Output is correct |
| 23 |
Correct |
19 ms |
13568 KB |
Output is correct |
| 24 |
Correct |
863 ms |
263180 KB |
Output is correct |
| 25 |
Correct |
703 ms |
259748 KB |
Output is correct |
| 26 |
Correct |
759 ms |
286280 KB |
Output is correct |
| 27 |
Correct |
743 ms |
259880 KB |
Output is correct |
| 28 |
Correct |
673 ms |
260540 KB |
Output is correct |
| 29 |
Correct |
1123 ms |
330368 KB |
Output is correct |
| 30 |
Correct |
993 ms |
404024 KB |
Output is correct |
| 31 |
Correct |
1066 ms |
330500 KB |
Output is correct |
