oj.uz

답안 #589706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589706 2022-07-05T07:11:20 Z 반딧불(#8407) 로카히아 유적 (FXCUP3_lokahia) C++17
13 / 100
 1120 ms 194188 KB 
#include "sungjin.h"
#include <bits/stdc++.h>

namespace {
    const int xx[]={0, 0, 1, -1};
    const int yy[]={1, -1, 0, 0};

    int n, m, k;
    int board[2002][2002];
    bool able[2002][2002];
    int num[2002][2002], numCnt;
}

void dfsAble(int x, int y){
    able[x][y] = 0;
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(tx<0 || ty<0 || tx>n+1 || ty>m+1 || !able[tx][ty]) continue;
        if(board[x][y] & (1<<d)) continue;
        if(board[tx][ty] & (1<<(d^1))) continue;
        dfsAble(tx, ty);
    }
}

void dfsGroup(int x, int y, int g){
    num[x][y] = g;
//    printf("%d %d: %d\n", x, y, g);
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(!able[tx][ty] || num[tx][ty] || (board[x][y] & (1<<d))) continue;
        dfsGroup(tx, ty, g);
    }
}

void Init(int N, int M, int W, int R[], int C[], int D[]){
	n = N, m = M, k = W;
	for(int i=0; i<k; i++){
        D[i]--;
        int x = R[i], y = C[i], d = D[i];
        board[x][y] |= (1<<d);
	}
    for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) able[i][j] = 1;
    dfsAble(0, 0);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!able[i][j] || num[i][j]) continue;
            dfsGroup(i, j, ++numCnt);
        }
    }
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	if(!able[R1][C1] || !able[R2][C2] || num[R1][C1] != num[R2][C2]) return false;
	return true;
}

#include "dowoon.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    const int xx[]={0, 0, 1, -1};
    const int yy[]={1, -1, 0, 0};

    int n, m;
    int link[2002][2002][4];
    int visited[2002][2002];
    int ans;
    int cnt;
}

void dfs(int x, int y){
    visited[x][y] = 1;
    cnt++;
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(!link[x][y][d] || visited[tx][ty]) continue;
        dfs(tx, ty);
    }
}

int Guess(int N, int M){
//    for(int i=1; i<=60000; i++){
//        printf("");
//    }
    n = N, m = M;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(i<n) link[i][j][2] = link[i+1][j][3] = Ask(i, j, i+1, j);
            if(j<m) link[i][j][0] = link[i][j+1][1] = Ask(i, j, i, j+1);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!visited[i][j]){
                cnt = 0;
                dfs(i, j);
                ans = max(ans, cnt);
            }
        }
    }
    return ans*2 > n*m;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 764 KB Correct
2 Correct 1 ms 788 KB Correct
3 Correct 25 ms 1412 KB Correct
4 Correct 67 ms 21484 KB Correct
5 Correct 61 ms 15380 KB Correct
6 Correct 309 ms 123676 KB Correct
7 Correct 306 ms 127004 KB Correct
8 Correct 326 ms 194188 KB Correct
9 Correct 299 ms 124668 KB Correct

Subtask #2
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 764 KB Correct
2 Correct 1 ms 788 KB Correct
3 Correct 25 ms 1412 KB Correct
4 Correct 67 ms 21484 KB Correct
5 Correct 61 ms 15380 KB Correct
6 Correct 309 ms 123676 KB Correct
7 Correct 306 ms 127004 KB Correct
8 Correct 326 ms 194188 KB Correct
9 Correct 299 ms 124668 KB Correct
10 Partially correct 691 ms 53620 KB Partially correct : C/MN = 1.550
11 Partially correct 46 ms 4188 KB Partially correct : C/MN = 1.500
12 Partially correct 19 ms 2536 KB Partially correct : C/MN = 1.467
13 Partially correct 4 ms 924 KB Partially correct : C/MN = 1.417
14 Partially correct 2 ms 656 KB Partially correct : C/MN = 1.333
15 Partially correct 2 ms 672 KB Partially correct : C/MN = 1.300
16 Partially correct 2 ms 648 KB Partially correct : C/MN = 1.250
17 Partially correct 2 ms 648 KB Partially correct : C/MN = 1.167
18 Correct 1 ms 648 KB Correct
19 Partially correct 1120 ms 101756 KB Partially correct : C/MN = 1.600
20 Correct 1 ms 796 KB Correct
21 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -