oj.uz

Submission #22686

# Submission time Handle Problem Language Result Execution time Memory
22686 2017-04-30T06:33:46 Z - - - - - - - List of honorable mention follows - - - - - - -(#999, xhae, ainu7, littlesheep) Young Zebra (KRIII5_YZ) C++11
2 / 7
 239 ms 88196 KB 
#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <cctype>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <queue>
#include <stdint.h>
#include <stdio.h>
#include <stack>
#include <ctime>
#include <list>
#include <map>
#include <set>
#include <tuple>
#include <unordered_set>
#include <assert.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define TR(i,x) for(__typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALL(x) x.begin(),x.end()
#define SORT(x) sort(ALL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))

using namespace std;

#define PB push_back
#define MP make_pair

typedef map<int,int> MII;
typedef map<string,int> MSI;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<long double> VD;
typedef pair<int,int> PII;
typedef long long int64;
typedef long long LL;
typedef unsigned int UI;
typedef long double LD;
typedef unsigned long long ULL;

const int N = 407 * 3;

char table[N][N];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int n, m;

void dfs(int x, int y, int result[N][N], bool allowTB, bool allowLR, int col) {
    result[x][y] = col;
    REP(d, 4) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if ((nx < 0 || nx >= n) && !allowTB) {
            continue;
        }
        nx = (nx + n) % n;
        if ((ny < 0 || ny >= m) && !allowLR) {
            continue;
        }
        ny = (ny + m) % m;
        if (table[nx][ny] != table[x][y]) {
            continue;
        }
        if (result[nx][ny] != -1) {
            assert(result[nx][ny] == col);
            continue;
        }
        dfs(nx, ny, result, allowTB, allowLR, col);
    }
}

void doDfs(int result[N][N], bool allowTB, bool allowLR) {
    REP(i, n) REP(j, m) result[i][j] = -1;
    int colors = 0;
    REP(i, n) REP(j, m) if (result[i][j] == -1) {
        dfs(i, j, result, allowTB, allowLR, colors++);
    }
}

int conn0[N][N];
int conn1[N][N];
int conn2[N][N];
int colorCount[N * N];

int main() {
    cin >> n >> m;
    REP(i, n) scanf("%s", table[i]);
    doDfs(conn0, true, true);
    REP(i, n * 3) REP(j, m * 3) table[i][j] = table[i % n][j % m];
    n *= 3; m *= 3;
    doDfs(conn1, true, true);
    n /= 3; m /= 3;
    REP(i, n) REP(j, m) ++colorCount[conn0[i][j]];
    REP(j, m) if (table[0][j] == table[n - 1][j]) {
        if (conn1[0][j] == conn1[n - 1][j]) {
            colorCount[conn0[0][j]] = -1;
        }
    }
    REP(i, n) if (table[i][0] == table[i][m - 1]) {
        if (conn1[i][0] == conn1[i][m - 1]) {
            colorCount[conn0[i][0]] = -1;
        }
    }
    REP(i, n) {
        REP(j, m) {
            if (j) printf(" ");
            printf("%d", colorCount[conn0[i][j]]);
        }
        printf("\n");
    }
    return 0;
}

Compilation message

YZ.cpp: In function 'int main()':
YZ.cpp:100:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     REP(i, n) scanf("%s", table[i]);
                                    ^

Subtask #1
2.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 46368 KB Output is correct
2 Correct 126 ms 71796 KB Output is correct
3 Partially correct 136 ms 46904 KB Output is partially correct
4 Partially correct 129 ms 32416 KB Output is partially correct
5 Correct 126 ms 29856 KB Output is correct
6 Correct 116 ms 29032 KB Output is correct
7 Correct 196 ms 48488 KB Output is correct
8 Correct 113 ms 77172 KB Output is correct
9 Correct 189 ms 88196 KB Output is correct
10 Correct 119 ms 36112 KB Output is correct
11 Correct 123 ms 39080 KB Output is correct
12 Correct 136 ms 39080 KB Output is correct
13 Correct 173 ms 43808 KB Output is correct
14 Correct 126 ms 39920 KB Output is correct
15 Correct 163 ms 42740 KB Output is correct
16 Correct 126 ms 34136 KB Output is correct
17 Correct 116 ms 45160 KB Output is correct
18 Correct 113 ms 45164 KB Output is correct
19 Correct 159 ms 26768 KB Output is correct
20 Correct 169 ms 40736 KB Output is correct
21 Correct 156 ms 51328 KB Output is correct
22 Correct 239 ms 50772 KB Output is correct
23 Correct 166 ms 38660 KB Output is correct
24 Correct 133 ms 42368 KB Output is correct
25 Correct 153 ms 64288 KB Output is correct
26 Correct 0 ms 26768 KB Output is correct
27 Correct 0 ms 26768 KB Output is correct
28 Correct 0 ms 28616 KB Output is correct
29 Correct 3 ms 28612 KB Output is correct
30 Correct 0 ms 26768 KB Output is correct
31 Correct 0 ms 26768 KB Output is correct
32 Correct 3 ms 26768 KB Output is correct
33 Correct 0 ms 26768 KB Output is correct
34 Correct 0 ms 26768 KB Output is correct
35 Correct 0 ms 26768 KB Output is correct
36 Correct 9 ms 30432 KB Output is correct
37 Correct 6 ms 28268 KB Output is correct
38 Correct 9 ms 26768 KB Output is correct
39 Correct 6 ms 27716 KB Output is correct
40 Correct 6 ms 30024 KB Output is correct