AtCoder Regular Contest 006

Submission #1390140

Source codeソースコード

#include <iostream>
#include <sstream>
#include <fstream>

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
// #include <unordered_map>
#include <set>
#include <utility>
#include <bitset>
#include <limits>
#include <climits>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define ALL(c)  (c).begin(),(c).end()


class UnionFind {
 public:
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    assert(0 <= x && x < data.size());
    assert(0 <= y && y < data.size());
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};


vector<int> solve(vvi& mp) {
    int R=mp.size()-2, C=mp[0].size()-2;
    UnionFind uf(R*C);

    rep(r,R) rep(c,C) {
        // printf("%d %d\n", r,c);
        if (!mp[1+r][1+c]) continue;

        if (mp[1+r-1][1+c-1]) uf.unionSet(r*C+c, (r-1)*C+(c-1));
        if (mp[1+r-1][1+c  ]) uf.unionSet(r*C+c, (r-1)*C+c);
        if (mp[1+r-1][1+c+1]) uf.unionSet(r*C+c, (r-1)*C+(c+1));
        if (mp[1+r  ][1+c-1]) uf.unionSet(r*C+c, r*C+(c-1));
        //
        if (mp[1+r  ][1+c+1]) uf.unionSet(r*C+c, r*C+(c+1));
        if (mp[1+r+1][1+c-1]) uf.unionSet(r*C+c, (r+1)*C+(c-1));
        if (mp[1+r+1][1+c  ]) uf.unionSet(r*C+c, (r+1)*C+c);
        if (mp[1+r+1][1+c+1]) uf.unionSet(r*C+c, (r+1)*C+(c+1));
    }

    vector<int> rmin(R*C, 1001), rmax(R*C, -1), cmin(R*C, 1001), cmax(R*C, -1);
    rep(r,R) rep(c,C) {
//        if (!mp[1+r][1+c]) continue;
        int root = uf.root(r*C+c);
        // if (uf.size(r*C+c))
        rmin[root] = min(rmin[root], r);
        rmax[root] = max(rmax[root], r);
        cmin[root] = min(cmin[root], c);
        cmax[root] = max(cmax[root], c);
    }

    // vector<int> w(R*C), h(R*C);
    int na=0, nb=0, nc=0;
    rep(i, R*C) {
        int area = -uf.data[i];
        if (area <= 1) continue;

        int w = cmax[i] - cmin[i] + 1;
        int h = rmax[i] - rmin[i] + 1;
        assert(w == h);
        int mag = w / 5;
        // printf("(i=%d) area=%d w=%d h=%d mag=%d\n", i,area,w,h,mag);
        assert(area % (mag*mag) == 0);
        area /= (mag*mag);
        switch (area) {
            case 12: ++na; break;
            case 16: ++nb; break;
            case 11: ++nc; break;
        }
    }

    return vector<int>{ na, nb, nc };
}

int main(){
    int R, C; cin >> R >> C;
    vvi mp(R+2, vi(C+2, 0));
    rep(r,R) {
        string s; cin>>s;
        // assert(s.size() == W);
        rep(c,C) {
            mp[1+r][1+c] = (s[c]=='o') ? 1 : 0;
        }
    }

    vector<int> res = solve(mp);
    printf("%d %d %d\n", res[0], res[1], res[2]);
    return 0;
}

Submission

Task問題 D - アルファベット探し
User nameユーザ名 naoya_t
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3442 Byte
File nameファイル名
Exec time実行時間 65 ms
Memory usageメモリ使用量 23680 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00_min.txt,00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,00_sample_04.txt,00_sample_05.txt,01_rndsmall_00.txt,01_rndsmall_01.txt,01_rndsmall_02.txt,01_rndsmall_03.txt,01_rndsmall_04.txt,01_rndsmall_05.txt,01_rndsmall_06.txt,01_rndsmall_07.txt,01_rndsmall_08.txt,01_rndsmall_09.txt,01_rndsmall_10.txt,01_rndsmall_11.txt,01_rndsmall_12.txt,01_rndsmall_13.txt,01_rndsmall_14.txt,01_rndsmall_15.txt,01_rndsmall_16.txt,01_rndsmall_17.txt,01_rndsmall_18.txt,01_rndsmall_19.txt,02_rndmax_00.txt,02_rndmax_01.txt,02_rndmax_02.txt,02_rndmax_03.txt,02_rndmax_04.txt,02_rndmax_05.txt,02_rndmax_06.txt,02_rndmax_07.txt,02_rndmax_08.txt,02_rndmax_09.txt,02_rndmax_10.txt,02_rndmax_11.txt,02_rndmax_12.txt,02_rndmax_13.txt,02_rndmax_14.txt,02_rndmax_15.txt,02_rndmax_16.txt,02_rndmax_17.txt,02_rndmax_18.txt,02_rndmax_19.txt,03_rnd_00.txt,03_rnd_01.txt,03_rnd_02.txt,03_rnd_03.txt,03_rnd_04.txt,03_rnd_05.txt,03_rnd_06.txt,03_rnd_07.txt,03_rnd_08.txt,03_rnd_09.txt,04_empty_00.txt,05_maxret_00.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_min.txt AC 1 ms 256 KB
00_sample_01.txt AC 1 ms 256 KB
00_sample_02.txt AC 1 ms 256 KB
00_sample_03.txt AC 1 ms 256 KB
00_sample_04.txt AC 1 ms 256 KB
00_sample_05.txt AC 1 ms 256 KB
01_rndsmall_00.txt AC 2 ms 512 KB
01_rndsmall_01.txt AC 2 ms 512 KB
01_rndsmall_02.txt AC 2 ms 512 KB
01_rndsmall_03.txt AC 2 ms 512 KB
01_rndsmall_04.txt AC 2 ms 512 KB
01_rndsmall_05.txt AC 2 ms 512 KB
01_rndsmall_06.txt AC 2 ms 512 KB
01_rndsmall_07.txt AC 2 ms 512 KB
01_rndsmall_08.txt AC 2 ms 512 KB
01_rndsmall_09.txt AC 2 ms 512 KB
01_rndsmall_10.txt AC 2 ms 512 KB
01_rndsmall_11.txt AC 2 ms 512 KB
01_rndsmall_12.txt AC 2 ms 512 KB
01_rndsmall_13.txt AC 2 ms 512 KB
01_rndsmall_14.txt AC 2 ms 512 KB
01_rndsmall_15.txt AC 2 ms 512 KB
01_rndsmall_16.txt AC 2 ms 512 KB
01_rndsmall_17.txt AC 2 ms 512 KB
01_rndsmall_18.txt AC 2 ms 512 KB
01_rndsmall_19.txt AC 2 ms 512 KB
02_rndmax_00.txt AC 56 ms 23680 KB
02_rndmax_01.txt AC 57 ms 23680 KB
02_rndmax_02.txt AC 59 ms 23680 KB
02_rndmax_03.txt AC 57 ms 23680 KB
02_rndmax_04.txt AC 58 ms 23680 KB
02_rndmax_05.txt AC 58 ms 23680 KB
02_rndmax_06.txt AC 62 ms 23680 KB
02_rndmax_07.txt AC 58 ms 23680 KB
02_rndmax_08.txt AC 57 ms 23680 KB
02_rndmax_09.txt AC 56 ms 23680 KB
02_rndmax_10.txt AC 56 ms 23680 KB
02_rndmax_11.txt AC 57 ms 23680 KB
02_rndmax_12.txt AC 58 ms 23680 KB
02_rndmax_13.txt AC 59 ms 23680 KB
02_rndmax_14.txt AC 65 ms 23680 KB
02_rndmax_15.txt AC 57 ms 23680 KB
02_rndmax_16.txt AC 57 ms 23680 KB
02_rndmax_17.txt AC 56 ms 23680 KB
02_rndmax_18.txt AC 57 ms 23680 KB
02_rndmax_19.txt AC 57 ms 23680 KB
03_rnd_00.txt AC 3 ms 896 KB
03_rnd_01.txt AC 14 ms 5376 KB
03_rnd_02.txt AC 14 ms 5120 KB
03_rnd_03.txt AC 16 ms 6144 KB
03_rnd_04.txt AC 18 ms 7040 KB
03_rnd_05.txt AC 5 ms 1664 KB
03_rnd_06.txt AC 23 ms 8960 KB
03_rnd_07.txt AC 8 ms 3072 KB
03_rnd_08.txt AC 33 ms 12672 KB
03_rnd_09.txt AC 27 ms 10624 KB
04_empty_00.txt AC 53 ms 23680 KB
05_maxret_00.txt AC 61 ms 23680 KB