oj.uz

Submission #72556

# Submission time Handle Problem Language Result Execution time Memory
72556 2018-08-26T09:00:01 Z imsifile Lokahian Rampart (FXCUP3_lokahia) C++17
13 / 100
 1483 ms 178528 KB 
#include "sungjin.h"

static int N, M, ba[1010][1010], chk[1010][1010], xx[4]={1,-1,0,0}, yy[4]={0,0,1,-1}; // DURL

static void dfs1(int x, int y){
	if(x<0 || y<0 || x>N+1 || y>M+1) return;
	if(chk[x][y]) return;
	chk[x][y]=-1;
	for(int i=0; i<4; i++){
		if(ba[x][y]&(1<<i)) continue;
		dfs1(x+xx[i], y+yy[i]);
	}
}

static int col;
static void dfs2(int x, int y){
	if(x<=0 || y<=0 || x>N || y>M) return;
	if(chk[x][y]) return;
	chk[x][y]=col;
	for(int i=0; i<4; i++) dfs2(x+xx[i], y+yy[i]);
}

void Init(int N_, int M_, int W, int R[], int C[], int dir[]) {
	N=N_, M=M_;
	for(int i=W; i--;){
		if(dir[i]==1) ba[R[i]][C[i]+1] |= 1<<3;
		if(dir[i]==2) ba[R[i]][C[i]-1] |= 1<<2;
		if(dir[i]==3) ba[R[i]+1][C[i]] |= 1<<1;
		if(dir[i]==4) ba[R[i]-1][C[i]] |= 1<<0;
	}
	dfs1(0,0);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(chk[i][j]) continue;
			++col; dfs2(i,j);
		}
	}
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	if(chk[R1][C1]<0 || chk[R2][C2]<0) return 0;
	return chk[R1][C1] == chk[R2][C2];
}

// ainta & cki86201's code (https://oj.uz/submission/72484)

    #include "dowoon.h"
     
    int w[1010][1010], c1, c2;
     
    void Put(int x, int y, int c) {
    	if (w[x][y])return;
    	w[x][y] = c;
    	if (c == 1)c1++;
    	else c2++;
    }
    int Guess(int N, int M) {
    	int i, j;
    	for (i = 1; i <= N; i++) {
    		for (j = 1; j <= M; j++) {
    			if (c1 * 2 > N*M)return 1;
    			if (c2 * 2 >= N*M)return 0;
    			if (w[i][j]) {
    				if (w[i][j] == 2) continue;
    				if (j + 1 <= M && !w[i][j + 1]) {
    					if (Ask(i, j, i, j + 1))Put(i,j+1,1);
    					else Put(i,j+1,2);
    				}
    				if (i + 1 <= N && !w[i + 1][j]) {
    					if (Ask(i, j, i + 1, j))Put(i+1,j,1);
    					else Put(i+1,j,2);
    				}
    				continue;
    			}
    			if (i == N && j == M) {
    				w[i][j] = 2;
    				continue;
    			}
    			if (i == N) {
    				if (Ask(i, j, i, j + 1)) {
    					Put(i, j, 1);
    					Put(i, j + 1, 1);
    				}
    				else Put(i, j, 2);
    				continue;
    			}
    			if (j == M) {
    				if (Ask(i, j, i + 1, j)) {
    					Put(i, j, 1);
    					Put(i + 1, j, 1);
    				}
    				else Put(i, j, 2);
    				continue;
    			}
    			int t1 = Ask(i, j, i + 1, j);
    			int t2 = Ask(i, j, i, j + 1);
    			if (t1 || t2) {
    				Put(i, j, 1);
    				if (t1)Put(i + 1, j, 1);
    				else Put(i + 1, j, 2);
    				if (t2)Put(i, j + 1, 1);
    				else Put(i, j + 1, 2);
    			}
    			else {
    				Put(i, j, 2);
    			}
    		}
    	}
    	if (c1 * 2 > N*M)return 1;
    	return 0;
    }

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 872 KB Correct
2 Correct 5 ms 1208 KB Correct
3 Correct 20 ms 1740 KB Correct
4 Correct 90 ms 16912 KB Correct
5 Correct 99 ms 16912 KB Correct
6 Correct 299 ms 68512 KB Correct
7 Correct 375 ms 96848 KB Correct
8 Correct 371 ms 140140 KB Correct
9 Correct 327 ms 173112 KB Correct

Subtask #2
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 872 KB Correct
2 Correct 5 ms 1208 KB Correct
3 Correct 20 ms 1740 KB Correct
4 Correct 90 ms 16912 KB Correct
5 Correct 99 ms 16912 KB Correct
6 Correct 299 ms 68512 KB Correct
7 Correct 375 ms 96848 KB Correct
8 Correct 371 ms 140140 KB Correct
9 Correct 327 ms 173112 KB Correct
10 Correct 987 ms 173112 KB Correct
11 Partially correct 52 ms 173112 KB Partially correct : C/MN = 1.188
12 Correct 28 ms 173112 KB Correct
13 Correct 10 ms 173112 KB Correct
14 Partially correct 6 ms 173112 KB Partially correct : C/MN = 1.222
15 Partially correct 5 ms 173112 KB Partially correct : C/MN = 1.100
16 Correct 5 ms 173112 KB Correct
17 Correct 5 ms 173112 KB Correct
18 Correct 5 ms 173112 KB Correct
19 Partially correct 1483 ms 175820 KB Partially correct : C/MN = 1.120
20 Correct 6 ms 178528 KB Correct
21 Correct 4 ms 178528 KB Correct
22 Correct 4 ms 178528 KB Correct
23 Correct 7 ms 178528 KB Correct
24 Correct 21 ms 178528 KB Correct
25 Runtime error 15 ms 178528 KB Execution failed because the return code was nonzero
26 Halted 0 ms 0 KB -