結果

問題 No.5002 stick xor
コンテスト
ユーザー sumoru
提出日時 2018-05-26 14:58:05
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 909 ms / 1,000 ms
コード長 5,438 bytes
コンパイル時間 33,520 ms
実行使用メモリ 1,580 KB
スコア 41,249
最終ジャッジ日時 2018-05-26 14:58:41
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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.9
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 {
    int a, b, c, 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&) const { return false; }
};

int main(){
    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 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 put = [&](Ans a){ 
        for(int y = a.a; y <= a.c; y++){
            for(int x = a.b; x <= a.d; x++){
                as[y][x] = !as[y][x];
            }
        }
    };
    auto findBest = [&](int l){ 
        pair<int, Ans> ret(-1, {});
        // int maxi = -1;
        for(int y = 0; y < n; y++){
            for(int x = 0; x < n - l; x++){
                pair<int, Ans> cand(0, {y, x, y, x + l - 1});
                // int cnt = 0;
                for(int j = 0; j < l; j++){
                    cand.first += as[y][x + j];
                    // cnt += as[y][x + j];
                }
                ret = max(ret, cand);
                // if(maxi < cnt){
                //     maxi = cnt;
                //     ret = {y, x, y, x + l - 1};
                // }
            }
        }
        for(int y = 0; y < n - l; y++){
            for(int x = 0; x < n; x++){
                pair<int, Ans> cand(0, {y, x, y + l - 1, x});
                // int cnt = 0;
                for(int j = 0; j < l; j++){
                    cand.first += as[y + j][x];
                    // cnt += as[y + j][x];
                }
                ret = max(ret, cand);
                // if(maxi < cnt){
                //     maxi = cnt;
                //     ret = {y, x, y + l - 1, x};
                // }
            }
        }
        return ret;
    };

    for(int i = 0; i < k; i++){
        put(ans[i] = findBest(ls[i]).second);
    }
    while(elapsed() < LIMIT){ for(int _ = 0; _ < 100; _++){
    // for(elapsed() < LIMIT){ for(int i = 0; i < 100; i++){
        int i = mt() % k;
        put(ans[i]);
        ans[i] = findBest(ls[i]).second;
        put(ans[i]);
        if(ans[i].a == ans[i].c){
            if(ans[i].d + 1 < n && as[ans[i].a][ans[i].b] && as[ans[i].a][ans[i].d + 1]){
                as[ans[i].a][ans[i].b] = !as[ans[i].a][ans[i].b];
                as[ans[i].a][ans[i].d + 1] = !as[ans[i].a][ans[i].d + 1];
                ans[i].b++; ans[i].d++;
            }
            if(ans[i].b && as[ans[i].a][ans[i].b - 1] && as[ans[i].a][ans[i].d]){
                as[ans[i].a][ans[i].b - 1] = !as[ans[i].a][ans[i].b - 1];
                as[ans[i].a][ans[i].d] = !as[ans[i].a][ans[i].d];
                ans[i].b--; ans[i].d--;
            }
        }
        if(ans[i].b == ans[i].d){
            if(ans[i].c + 1 < n && as[ans[i].a][ans[i].b] && as[ans[i].c + 1][ans[i].b]){
                as[ans[i].a][ans[i].b] = !as[ans[i].a][ans[i].b];
                as[ans[i].c + 1][ans[i].b] = !as[ans[i].c + 1][ans[i].b];
                ans[i].a++; ans[i].c++;
            }
            if(ans[i].a && as[ans[i].a - 1][ans[i].b] && as[ans[i].c][ans[i].b]){
                as[ans[i].a - 1][ans[i].b] = !as[ans[i].a - 1][ans[i].b];
                as[ans[i].c][ans[i].b] = !as[ans[i].c][ans[i].b];
                ans[i].a--; ans[i].c--;
            }
        }
    } }
    for(auto& e : ans){
        cout << e << '\n';
    }
    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);
}
0