답안 #27183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
27183	2017-07-10T02:21:47 Z	검수컵(#1129)	On the Grid (FXCUP2_grid)	C++	0 / 1	2000 ms	3152 KB

grid

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

int N, Q, row[101010], col[101010]; // A, B, ..., EXQD is actually?

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

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

map<int,int> pois;

void find_bound(int dir, int gap, int y, int &left, int &right){
	for(int j=y;; j--){
		int i = gap;
		if(dir < 0) i += j;
		else i -= j;
		if(pois[i] != j){ left=j; break; }
	}
	for(int j=y;; j++){
		int i = gap;
		if(dir < 0) i += j;
		else i -= j;
		if(pois[i] != j){ right=j; break; }
	}
}

int main(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++){
		row[i] = col[i] = i;
		pois[i] = i;
	}
	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);
			swap(row[p], row[q]);
			pois[row[p]] = col[p]; pois[row[q]] = col[q];
		}
		if(typ == 2){
			scanf("%d%d", &p, &q);
			swap(col[p], col[q]);
			pois[row[p]] = col[p]; pois[row[q]] = col[q];
		}
		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(-1, row[1]-col[1], col[1], yl, yr);
			xl = row[1]-col[1]+yl, xr = row[1]-col[1]+yr;
		}
		else{
			find_bound(1, row[1]+col[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:44: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:51:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &typ);
                    ^
grid.cpp:53: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:58:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &p, &q);
                         ^

Subtask #1

0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1964 KB	Output is correct
2	Correct	0 ms	1964 KB	Output is correct
3	Correct	0 ms	1964 KB	Output is correct
4	Correct	3 ms	1964 KB	Output is correct
5	Correct	3 ms	2096 KB	Output is correct
6	Execution timed out	2000 ms	3152 KB	Execution timed out
7	Halted	0 ms	0 KB	-