CODE FESTIVAL 2016 Final

Submission #995271

Source codeソースコード

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

template<class T>
T pow(T x, ll n, T r = 1) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

// using B = vector<string>;
// set<B> s;
// void dfs(B b) {
//     if (s.count(b)) return;
//     s.insert(b);
//     cout << b[0] << endl << b[1] << endl;
//     swap(b[0][0], b[0][1]);
//     dfs(b);
//     swap(b[0][0], b[0][1]);
//     swap(b[0][0], b[1][0]);
//     dfs(b);
//     swap(b[0][0], b[1][0]);
//     swap(b[1][0], b[1][1]);
//     dfs(b);
//     swap(b[1][0], b[1][1]);
//     swap(b[0][1], b[1][1]);
//     dfs(b);
//     swap(b[0][1], b[1][1]);
// }

const int MN = 220;
using P = pair<int, int>;

Mint off = 1;

int co(vector<char> v) {
    sort(v.begin(), v.end());
/*    for (char c: v) {
        cout << c;
    } cout << endl;*/
    set<vector<char>> s;
    do {
        s.insert(v);
    } while (next_permutation(v.begin(), v.end()));
    return int(s.size());
}

bool coun(vector<char> v) {
    int u = co(v);
    if (u != 24) {
        off *= u;
        return false;
    }
    return true;
}

char g[MN][MN];
Mint d[MN][MN];

int main() {
    cout << setprecision(20);
    int h, w;
    cin >> h >> w;

    for (int y = 0; y < h; y++) {
        string s;
        cin >> s;
        for (int x = 0; x < w; x++) {
            g[y][x] = s[x];
        }
    }

    if (h % 2) {
        string s1, s2;
        for (int x = 0; x < w; x++) {
            s1 += g[h/2][x];
            s2 += g[h/2][w-1-x];
        }
        if (s1 != s2) off *= 2;
    }
    if (w % 2) {
        string s1, s2;
        for (int x = 0; x < h; x++) {
            s1 += g[x][w/2];
            s2 += g[h-1-x][w/2];
        }
        if (s1 != s2) off *= 2;
    }

    if (min(h, w) == 1) {
        cout << off.v << endl;
        return 0;
    }

    int buf = 0;
    vector<int> yv, xv;
    for (int a = 0; a < h; a++) {
        int b = h-1-a;
        if (a >= b) continue;
        for (int c = 0; c < w; c++) {
            int d = w-1-c;
            if (c >= d) continue;
            vector<char> v;
            v.push_back(g[a][c]);
            v.push_back(g[a][d]);
            v.push_back(g[b][c]);
            v.push_back(g[b][d]);
            bool u = coun(v);
            if (u) {
                yv.push_back(a);
                xv.push_back(c);
                off *= 12;
            }
        }
    }
    sort(yv.begin(), yv.end());
    yv.erase(unique(begin(yv), end(yv)), end(yv));
    sort(xv.begin(), xv.end());
    xv.erase(unique(begin(xv), end(xv)), end(xv));

    int co = yv.size()+xv.size();
    co--;
    if (co >= 0) {
        off *= pow(Mint(2), co);
    }
    cout << off.v << endl;
    return 0;
}

Submission

Task問題 I - Reverse Grid
User nameユーザ名 ( : p )ミ
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1900
Source lengthソースコード長 4041 Byte
File nameファイル名
Exec time実行時間 28 ms
Memory usageメモリ使用量 640 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
all 1900 / 1900 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 2 ms 384 KB
01-02.txt AC 2 ms 384 KB
01-03.txt AC 2 ms 384 KB
01-04.txt AC 2 ms 384 KB
01-05.txt AC 2 ms 384 KB
01-06.txt AC 3 ms 384 KB
01-07.txt AC 2 ms 384 KB
01-08.txt AC 2 ms 512 KB
01-09.txt AC 2 ms 512 KB
01-10.txt AC 7 ms 512 KB
01-11.txt AC 11 ms 512 KB
01-12.txt AC 11 ms 512 KB
01-13.txt AC 7 ms 512 KB
01-14.txt AC 8 ms 512 KB
01-15.txt AC 8 ms 512 KB
01-16.txt AC 27 ms 640 KB
01-17.txt AC 27 ms 640 KB
01-18.txt AC 27 ms 640 KB
01-19.txt AC 16 ms 512 KB
01-20.txt AC 16 ms 512 KB
01-21.txt AC 16 ms 512 KB
01-22.txt AC 3 ms 384 KB
01-23.txt AC 12 ms 512 KB
01-24.txt AC 21 ms 512 KB
01-25.txt AC 21 ms 512 KB
01-26.txt AC 21 ms 512 KB
01-27.txt AC 4 ms 384 KB
01-28.txt AC 6 ms 512 KB
01-29.txt AC 3 ms 512 KB
01-30.txt AC 8 ms 512 KB
01-31.txt AC 28 ms 640 KB
01-32.txt AC 28 ms 640 KB
01-33.txt AC 28 ms 640 KB
01-34.txt AC 28 ms 640 KB
01-35.txt AC 28 ms 640 KB
sample-01.txt AC 2 ms 384 KB
sample-02.txt AC 2 ms 384 KB