답안 #27182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27182 2017-07-10T02:20:24 Z 검수컵(#1129) On the Grid (FXCUP2_grid) C++
1 / 1
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);
                         ^
# 결과 실행 시간 메모리 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