結果

問題 No.5002 stick xor
ユーザー sumorusumoru
提出日時 2018-05-27 12:40:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 959 ms / 1,000 ms
コード長 13,561 bytes
コンパイル時間 34,417 ms
実行使用メモリ 1,604 KB
スコア 44,555
最終ジャッジ日時 2018-05-27 12:41:24
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 956 ms
1,600 KB
testcase_01 AC 957 ms
1,600 KB
testcase_02 AC 957 ms
1,604 KB
testcase_03 AC 956 ms
1,604 KB
testcase_04 AC 957 ms
1,604 KB
testcase_05 AC 954 ms
1,600 KB
testcase_06 AC 955 ms
1,604 KB
testcase_07 AC 955 ms
1,604 KB
testcase_08 AC 954 ms
1,604 KB
testcase_09 AC 956 ms
1,604 KB
testcase_10 AC 955 ms
1,604 KB
testcase_11 AC 955 ms
1,604 KB
testcase_12 AC 955 ms
1,604 KB
testcase_13 AC 955 ms
1,600 KB
testcase_14 AC 956 ms
1,600 KB
testcase_15 AC 955 ms
1,604 KB
testcase_16 AC 957 ms
1,600 KB
testcase_17 AC 954 ms
1,600 KB
testcase_18 AC 956 ms
1,600 KB
testcase_19 AC 959 ms
1,604 KB
testcase_20 AC 957 ms
1,600 KB
testcase_21 AC 955 ms
1,604 KB
testcase_22 AC 955 ms
1,604 KB
testcase_23 AC 955 ms
1,604 KB
testcase_24 AC 956 ms
1,600 KB
testcase_25 AC 956 ms
1,604 KB
testcase_26 AC 956 ms
1,604 KB
testcase_27 AC 955 ms
1,600 KB
testcase_28 AC 956 ms
1,604 KB
testcase_29 AC 955 ms
1,600 KB
testcase_30 AC 955 ms
1,600 KB
testcase_31 AC 958 ms
1,604 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<random>
#include<sys/time.h>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ in >> p.first >> p.second; return in; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

#define LIMIT 0.95
mt19937 mt;
timeval start;
double elapsed(){
    timeval now;
    gettimeofday(&now, nullptr);
    return (now.tv_sec - start.tv_sec) + (now.tv_usec - start.tv_usec) / 1e6;
}

struct Ans {
    char a, b, c, d;
    Ans() = default;
    Ans(int a, int b, int c, int d): a(a), b(b), c(c), d(d) {}
    friend ostream& operator << (ostream& out, Ans& e) {
        return out << e.a + 1 << ' ' << e.b + 1 << ' ' << e.c + 1 << ' ' << e.d + 1;
    }
    bool operator == (const Ans& e) const {
        // return *(int*)(this) == *(int*)(&e);
        return a == e.a && b == e.b && c == e.c && d == e.d;
    }
    bool operator < (const Ans&) const { return false; }
};

int main(){
    // mt = mt19937(random_device()());
    gettimeofday(&start, nullptr);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> ls(k); cin >> ls;
    vector<string> as(n); cin >> as;
    for(auto& a : as){ for(auto& e : a){ e -= '0'; } }
    auto as0 = as;
    auto calc = [&](){ 
        int num = 0;
        for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){
            num += as[i][j];
        } }
        return num;
    };
    int score0 = calc();
    vector<Ans> ans(k);
    // vector<pair<int, int>> ps(k);
    // for(int i = 0; i < k; i++){
    //     ps[i] = {ls[i], i};
    // }
    // sort(ps.rbegin(), ps.rend());
    // for(auto p : ps){
    //     int i = p.second;

    auto rev = [](auto& e){ 
        e = !e;
    };
    auto put = [&](Ans a){ 
        int ret = 0;
        // if(a.a == a.c){
        //     for(int x = a.b; x <= a.d; x++){
        //         rev(as[a.a][x]);
        //         ret += (as[a.a][x] << 1) - 1;
        //     }
        // }else{
        //     for(int y = a.a; y <= a.c; y++){
        //         rev(as[y][a.b]);
        //         ret += (as[y][a.b] << 1) - 1;
        //     }
        // }
        for(int y = a.a; y <= a.c; y++){
            for(int x = a.b; x <= a.d; x++){
                rev(as[y][x]);
                ret += as[y][x] * 2 - 1;
            }
        }
        return ret;
    };
    auto findBestFast = [&](int l){ 
        pair<int, Ans> ret(-1, {});
        for(int y = 0; y < n; y++){
            pair<int, Ans> cand(0, Ans{y, 0, y, l - 1});
            for(int j = 0; j < l; j++){
                cand.first += as[y][j];
            }
            cand.first -= (as[y][0] && y && as[y - 1][0] && y + 1 < n && as[y + 1][0]) + as[y][l];
            ret = max(ret, cand);
            for(int x = 1; x < n - l + 1; x++){
                cand.first -= as[y][x - 1];
                cand.first += as[y][x + l - 1];
                cand.first += (as[y][x - 1] && (y && as[y - 1][x - 1] && y + 1 < n && as[y + 1][x - 1])) + as[y][l + x - 1];
                cand.first -= (as[y][x] && (y && as[y - 1][x] && y + 1 < n && as[y + 1][x])) + (l + x < n && as[y][l + x]);
                cand.second.b++;
                cand.second.d++;
                ret = max(ret, cand);
            }
        }
        for(int x = 0; x < n; x++){
            pair<int, Ans> cand(0, Ans{0, x, l - 1, x});
            for(int j = 0; j < l; j++){
                cand.first += as[j][x];
            }
            cand.first -= (as[0][x] && x && as[0][x - 1] && x + 1 < n && as[0][x + 1]) + as[l][x];
            for(int y = 1; y < n - l + 1; y++){
                cand.first -= as[y - 1][x];
                cand.first += as[y + l - 1][x];
                cand.first += (as[y - 1][x] && x && as[y - 1][x - 1] && x + 1 < n && as[y - 1][x + 1]) + as[l + y - 1][x];
                cand.first -= (as[y][x] && x && as[y][x - 1] && x + 1 < n && as[y][x + 1]) + (l + y < n && as[l + y][x]);
                cand.second.a++;
                cand.second.c++;
                ret = max(ret, cand);
            }
        }
        return ret;
    };
    auto findBest = [&](int l){ 
        pair<int, Ans> ret(-1, {});
        for(int y = 0; y < n; y++){
            for(int x = 0; x < n - l; x++){
                pair<int, Ans> cand(0, Ans{y, x, y, x + l - 1});
                for(int j = 0; j < l; j++){
                    cand.first += as[y][x + j] * 2;
                    cand.first += l > 2 && !as[y][x + j] && y && as[y - 1][x + j] && y + 1 < n && as[y + 1][x + j];
                }
                ret = max(ret, cand);
            }
        }
        for(int y = 0; y < n - l; y++){
            for(int x = 0; x < n; x++){
                pair<int, Ans> cand(0, Ans{y, x, y + l - 1, x});
                for(int j = 0; j < l; j++){
                    cand.first += as[y + j][x] * 2;
                    cand.first += l > 2 && !as[y + j][x] && x && as[y + j][x - 1] && x + 1 < n && as[y + j][x + 1];
                }
                ret = max(ret, cand);
            }
        }
        return ret;
    };
    auto findGood = [&](int l){ 
        pair<int, Ans> ra(-1, {}), rb(-1, {});
        // vector<pair<int, Ans>> rets(2, pair<int, Ans>(-1, {}));
        for(int y = 0; y < n; y++){
            pair<int, Ans> cand(0, Ans{y, 0, y, l - 1});
            for(int j = 0; j < l; j++){
                cand.first += as[y][j];
            }
            ra = cand;
            for(int x = 1; x < n - l + 1; x++){
                cand.first -= as[y][x - 1];
                cand.first += as[y][x + l - 1];
                cand.second.b++;
                cand.second.d++;
                if(rb < cand){
                    rb = cand;
                    if(ra < rb){
                        swap(ra, rb);
                    }
                }
            }
        }
        for(int x = 0; x < n; x++){
            pair<int, Ans> cand(0, Ans{0, x, l - 1, x});
            for(int j = 0; j < l; j++){
                cand.first += as[j][x];
            }
            if(rb < cand){
                rb = cand;
                if(ra < rb){
                    swap(ra, rb);
                }
            }
            for(int y = 1; y < n - l + 1; y++){
                cand.first -= as[y - 1][x];
                cand.first += as[y + l - 1][x];
                cand.second.a++;
                cand.second.c++;
                if(rb < cand){
                    rb = cand;
                    if(ra < rb){
                        swap(ra, rb);
                    }
                }
            }
        }
        return mt() & 1 ? ra : rb;
        // return rets[mt() % 2];
    };

        // for(int i = 0; i < k; i++){
        //     put(ans[i] = findBest(ls[i]).second);
        // }
        // printde(score0 - calc());
    int maxi = 0;
    auto as1 = as;
    auto ans1 = ans;
    vector<int> is, is2, is3;
    int thre = 7, thre2 = 2;
    for(int i = 0; i < k; i++){
        (ls[i] > thre ? is : ls[i] > thre2 ? is2 : is3).push_back(i);
    }
    // vector<int> is(k); iota(is.begin(), is.end(), 0);
    for(int _ = 0; _ < 10; _++){
        // int c2 = 0;
        as = as0;
        for(auto i : is){
            auto p = findBestFast(ls[i]);
            // auto p = findBest(ls[i]);
            // c2 += p.first * 2 - ls[i] < -6;
            // if(p.first * 2 - ls[i] < 1 && (ls[i] == 25 || ls[i] == 23)){
            //     p.second = {0, 0, 0, ls[i] - 1};
            //     c2++;
            // }
            // if(p.first * 2 - ls[i] < -6){
            //     p.second = {0, 0, 0, ls[i] - 1};
            //     // printde(ls[i]);
            // }
            put(ans[i] = p.second);
        }
        int cand = score0 - calc();
        if(maxi < cand){
            maxi = cand;
            ans1 = ans;
            as1 = as;
        }
        printde(cand);
        shuffle(is.begin(), is.end(), mt);
    // printde(c2);
    }
    as = as1;
    ans = ans1;

    int cnt = 0;
    double d;
    while((d = elapsed()) < LIMIT * 0.6){ for(int _ = 0; _ < 100; _++){
    // for(elapsed() < LIMIT){ for(int i = 0; i < 100; i++){
        cnt++;
        int i = is[mt() % is.size()];
        auto& a = ans[i];
        int diff = put(a);
        // auto a2 = findBestFast(ls[i]).second;
        auto a2 = findGood(ls[i]).second;
        // a = findBest(ls[i]).second;
        diff += put(a2);
        // static const double startT = 10, endT = 0.01;
        // double temp = startT + (endT - startT) * min(1.0, elapsed() / LIMIT);
        // if(exp(diff / temp) * (1ull << 32) > mt()){
        // if(diff > 1){
        if(diff > (d < LIMIT * 0.4)){
            put(a2);
            put(a);
            continue;
        }else{
            a = a2;
        }
        if(a.a == a.c){
            if(a.d + 1 < n && as[a.a][a.b] && (as[a.a][a.d + 1] || (a.a && as[a.a - 1][a.d] && a.a + 1 < n && as[a.a + 1][a.d]))){
            // if(a.d + 1 < n && as[a.a][a.b] && as[a.a][a.d + 1]){
                rev(as[a.a][a.b]);
                rev(as[a.a][a.d + 1]);
                a.b++; a.d++;
            }else if(a.b && as[a.a][a.b - 1] && as[a.a][a.d]){
                rev(as[a.a][a.b - 1]);
                rev(as[a.a][a.d]);
                a.b--; a.d--;
            }
        }
        if(a.b == a.d){
            if(a.c + 1 < n && as[a.a][a.b] && as[a.c + 1][a.b]){
                rev(as[a.a][a.b]);
                rev(as[a.c + 1][a.b]);
                a.a++; a.c++;
            }else if(a.a && as[a.a - 1][a.b] && as[a.c][a.b]){
                rev(as[a.a - 1][a.b]);
                rev(as[a.c][a.b]);
                a.a--; a.c--;
            }
        }
    } }
    printde(cnt);

    // vector<pair<double, int>> rs;
    // for(int i = 0; i < k; i++){
    //     int cnt = 0;
    //     for(int y = ans[i].a; y <= ans[i].c; y++){
    //         for(int x = ans[i].b; x <= ans[i].d; x++){
    //             cnt += as[y][x];
    //         }
    //     }
    //     rs.emplace_back(1. * cnt / ls[i], i);
    // }
    // sort(rs.rbegin(), rs.rend());
    // for(int i = 0; i < 10; i++){
    //     printe(rs[i].first, ls[rs[i].first]);
    // }
    int score = score0 - calc();
    printde(score);
    // vector<pair<int, int>> ps;
    // for(auto i : is2){
    //     ps.emplace_back(ls[i], i);
    // }
    // sort(ps.rbegin(), ps.rend());
    // for(auto& p : ps){
    //     put(ans[p.second] = findBest(p.first).second);
    // }

    // for(auto i : is2){
    //     put(ans[i] = findBest(ls[i]).second);
    // }
    // score = score0 - calc();
    // printde(score);

    as0 = as;
    maxi = 0;
    for(int _ = 0; _ < 10; _++){
        as = as0;
        for(auto i : is2){
            // put(ans[i] = findBestFast(ls[i]).second);
            put(ans[i] = findBest(ls[i]).second);
        }
        int cand = score0 - calc();
        if(maxi < cand){
            maxi = cand;
            ans1 = ans;
            as1 = as;
        }
        printde(cand);
        shuffle(is2.begin(), is2.end(), mt);
    }
    as = as1;
    ans = ans1;

    while((d = elapsed()) < LIMIT){ for(int _ = 0; _ < 100; _++){
        int i = mt() % k;
        if(ans[i] == Ans()){ continue; }
        // if(ls[i] <= thre2){ continue; }
        auto& a = ans[i];
        put(a);
        a = findBestFast(ls[i]).second;
        // a = findBest(ls[i]).second;
        put(a);
        // int diff = put(a);
        // auto a2 = findGood(ls[i]).second;
        // // a = findBest(ls[i]).second;
        // diff += put(a2);
        // if(diff > (d < LIMIT * 0.85)){
        //     put(a2);
        //     put(a);
        //     continue;
        // }else{
        //     a = a2;
        // }
        if(a.a == a.c){
            if(a.d + 1 < n && as[a.a][a.b] && as[a.a][a.d + 1]){
                rev(as[a.a][a.b]);
                rev(as[a.a][a.d + 1]);
                a.b++; a.d++;
            }else if(a.b && as[a.a][a.b - 1] && as[a.a][a.d]){
                rev(as[a.a][a.b - 1]);
                rev(as[a.a][a.d]);
                a.b--; a.d--;
            }
        }
        if(a.b == a.d){
            if(a.c + 1 < n && as[a.a][a.b] && as[a.c + 1][a.b]){
                rev(as[a.a][a.b]);
                rev(as[a.c + 1][a.b]);
                a.a++; a.c++;
            }else if(a.a && as[a.a - 1][a.b] && as[a.c][a.b]){
                rev(as[a.a - 1][a.b]);
                rev(as[a.c][a.b]);
                a.a--; a.c--;
            }
        }
    } }

    score = score0 - calc();
    printde(score);

    vector<pair<int, int>> ps;
    for(auto i : is3){
        ps.emplace_back(ls[i], i);
    }
    sort(ps.rbegin(), ps.rend());
    // sort(ps.begin(), ps.end());
    for(auto& p : ps){
        int i = p.second;
        // printde(findBest(ls[i]).first * 2 - ls[i], ls[i]);
        put(ans[i] = findBestFast(ls[i]).second);
        // put(ans[i] = findBest(ls[i]).second);
    }

    score = score0 - calc();
    printde(score);
    for(auto& e : ans){
        cout << e << '\n';
    }
}
0