Submission #72915

#	Time	Username	Problem	Language	Result	Execution time	Memory
72915		ainta	Lokahian Rampart (FXCUP3_lokahia)	C++17	88 / 100	1271 ms	217384 KiB

sungjin

#include "sungjin.h"

static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];

static int w[1010][1010][4], dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };

static int Rev[4] = { 1,0,3,2 };

void DFS(int x, int y) {
	if (x<0 || y<0 || x>n + 1 || y>m + 1 || vis[x][y])return;
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		if(!w[x][y][i])DFS(x + dx[i], y + dy[i]);
	}
}


void Go(int x, int y, int col) {
	vis[x][y] = col;
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if(!vis[tx][ty])Go(x + dx[i], y + dy[i], col);
	}
}

void Init(int N, int M, int W, int R[], int C[], int dir[]) {
	int i, j, res = 0;
	n = N, m = M;
	for (i = 0; i < W; i++) {
		dir[i]--;
		w[R[i]+dx[dir[i]]][C[i]+dy[dir[i]]][Rev[dir[i]]] = 1;
	}
	DFS(0, 0);
	int cnt = 1;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (!vis[i][j]) {
				cnt++;
				Go(i, j, cnt);
			}
		}
	}
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	if (vis[R1][C1] == vis[R2][C2] && vis[R1][C1] != 1)return 1;
	return 0;
}

dowoon

#include "dowoon.h"
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

static int UF[1010000], C[1010000], w[1010][1010], sum, vis[1010][1010];

static int n, m, cnt, dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

int Num(int x, int y) {
	return (x - 1)*m + y;
}
int Ask2(int a, int b, int c, int d) {
	if (sum * 2 >= n*m || cnt * 2 > n*m)return 0;
	return Ask(a, b, c, d);
}
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
void Merge(int a, int b, int c, int d) {
	w[a][b] = w[c][d] = 1;
	int x = Num(a, b), y = Num(c, d);
	x = Find(x), y = Find(y);
	if(x!=y)UF[x] = y;
}

static struct point {
	int x, y;
}P[1010][1010];

void Put(int a, int b, int c) {
	if (sum * 2 >= n*m || cnt * 2 > n*m)return;
	if (w[a][b])return;
	w[a][b] = c;
	point tp = P[a][b];
	if (tp.x && c == 1) {
		Put(tp.x, tp.y, 2);
	}
	if (c == 2) {
		if (!tp.x || w[tp.x][tp.y] == 2) sum++;
	}
}

void DDFS(int x, int y) {
	int i;
	vis[x][y] = 1;
	cnt++;
	for (i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if (1 > tx || tx > n || 1 > ty || ty > m ||vis[tx][ty]||w[tx][ty]==2)continue;
		if (!w[tx][ty]) {
			if (Ask2(x, y, tx, ty)) Put(tx, ty, 1);
			else Put(tx, ty, 2);
		}
		if (w[tx][ty] == 1 && !vis[tx][ty])DDFS(tx, ty);
	}
}


void Go(int x, int y) {
	cnt = 0;
	if (vis[x][y])return;
	if (n % 2 == 1 && m % 2 == 1 && x==n && y==m) {
		if (Ask2(x - 1, y, x, y)) {
			Put(x - 1, y, 1);
			Put(x, y, 1);
		}
		else{
			if (Ask2(x, y, x, y - 1)) {
				Put(x, y, 1);
				Put(x, y - 1, 1);
				Put(x - 1, y, 2);
			}
			else return;
		}
	}
	DDFS(x, y);
}

int Guess(int N, int M) {
	int i, j;
	n = N, m = M;
	vector<point>V;
	for (i = 1; i <= N*M; i++)UF[i] = i; 

	for (i = 1; i <= N; i++){
		for (j = 1; j < M; j += 2) {
			if (Ask2(i, j, i, j + 1)) {
				Put(i, j, 1);
				Put(i, j + 1, 1);
				V.push_back({ i, j });
			}
			else sum++;
			P[i][j] = { i,j + 1 };
			P[i][j + 1] = { i,j };
		}
	}
	if (M % 2 == 1) {
		for (i = 1; i < N; i+=2) {
			if (Ask2(i, M, i + 1, M)) {
				Put(i, M, 1);
				Put(i + 1, M, 1);
				V.push_back({ i, M });
			}
			else sum++;
			P[i][M] = { i + 1,M };
			P[i + 1][M] = { i,M };
		}
		if (N % 2 == 1) {
			V.push_back({ n,m });
		}
	}
	for (auto &t : V) {
		Go(t.x, t.y);
		if (cnt * 2 > n*m)return 1;
		sum += cnt;
		if (sum * 2 >= n*m)return 0;
	}
	return 0;
}

Compilation message (stderr)

sungjin.cpp: In function 'void Init(int, int, int, int*, int*, int*)':
sungjin.cpp:27:12: warning: unused variable 'res' [-Wunused-variable]
  int i, j, res = 0;
            ^~~
sungjin.cpp: At global scope:
sungjin.cpp:3:65: warning: 'U' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
                                                                 ^
sungjin.cpp:3:27: warning: 'Y' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
                           ^
sungjin.cpp:3:12: warning: 'X' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
            ^

dowoon.cpp:7:25: warning: 'C' defined but not used [-Wunused-variable]
 static int UF[1010000], C[1010000], w[1010][1010], sum, vis[1010][1010];
                         ^

• Subtask 1: 13 / 13
• Subtask 2: 75 / 87