結果

問題 No.5002 stick xor
ユーザー gazelle
提出日時 2018-05-31 01:38:47
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 972 ms / 1,000 ms
コード長 3,765 bytes
コンパイル時間 34,694 ms
実行使用メモリ 1,592 KB
スコア 17,163
最終ジャッジ日時 2018-05-31 01:39:24
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<random>
#include<time.h>
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<(ll)m; i++)
#define FOR(i,n,m) for(long long i=n; i<(ll)m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
struct cell {
    int row;
    int col;
};
enum dir {
    HORIZONTAL,
    VERTICAL,
};
struct op {
    dir d;
    cell c;
};
int n,k;
int l[500];
int a[60][60];
op ret[500];
int rd() {
    static random_device rd;
    static mt19937 mt(rd());
    return abs((int)mt());
}
int counter(dir d, cell c, int lgt, bool flag) {
    if(c.row<0||c.row>=n||c.col<0||c.col>=n) return -INF;
    if(d==HORIZONTAL&&c.col+lgt>n) return -INF;
    if(d==VERTICAL&&c.row+lgt>n) return -INF;
    int ret=0;
    if(d==HORIZONTAL) REP(i,lgt) ret+=flag^!a[c.row][c.col+i];
    if(d==VERTICAL) REP(i,lgt) ret+=flag^!a[c.row+i][c.col];
    return ret;
}
void update(int updidx, op o, int lgt) {
    dir d=o.d;
    cell c=o.c;
    if(d==HORIZONTAL) REP(i,lgt) a[c.row][c.col+i]^=1;
    if(d==VERTICAL) REP(i,lgt) a[c.row+i][c.col]^=1;
    switch(updidx) {
        case 0: { d=(d==HORIZONTAL ? VERTICAL : HORIZONTAL); break; }
        case 1: { c.row--; break; }
        case 2: { c.row++; break; }
        case 3: { c.col--; break; }
        case 4: { c.col++; break; }
        default: ;
    }
    if(d==HORIZONTAL) REP(i,lgt) a[c.row][c.col+i]^=1;
    if(d==VERTICAL) REP(i,lgt) a[c.row+i][c.col]^=1;
    return;
}
op newop(op o, int lgt) {
    dir d=o.d;
    cell c=o.c;
    int cnt=counter(d,c,lgt,0);
    int maxupd=0,updidx=-1,buf=0;
    buf=counter((dir)!d,c,lgt,1)-cnt;
    if(buf>maxupd) { maxupd=buf; updidx=0; }
    buf=counter(d,{c.row-1,c.col},lgt,1)-cnt;
    if(buf>maxupd) { maxupd=buf; updidx=1; }
    buf=counter(d,{c.row+1,c.col},lgt,1)-cnt;
    if(buf>maxupd) { maxupd=buf; updidx=2; }
    buf=counter(d,{c.row,c.col-1},lgt,1)-cnt;
    if(buf>maxupd) { maxupd=buf; updidx=3; }
    buf=counter(d,{c.row,c.col+1},lgt,1)-cnt;
    if(buf>maxupd) { maxupd=buf; updidx=4; }
    if(updidx!=-1) update(updidx,o,lgt);
    switch(updidx) {
        case 0: return {(dir)!d,c};
        case 1: return {d,{c.row-1,c.col}};
        case 2: return {d,{c.row+1,c.col}};
        case 3: return {d,{c.row,c.col-1}};
        case 4: return {d,{c.row,c.col+1}};
        default: return o;
    }
}
void input() {
    cin>>n>>k;
    REP(i,k) cin>>l[i];
    REP(i,n) REP(j,n) {
        char c;
        cin>>c;
        a[i][j]=(int)(c-'0');
    }
}
void output(op o, int lgt) {
    o.c.row++;
    o.c.col++;
    if(o.d==HORIZONTAL) cout<<o.c.row<<" "<<o.c.col<<" "<<o.c.row<<" "<<o.c.col+lgt-1<<endl;
    else cout<<o.c.row<<" "<<o.c.col<<" "<<o.c.row+lgt-1<<" "<<o.c.col<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    input();
    REP(i,k) {
        if(rd()%2) {
            ret[i].d=HORIZONTAL;
            ret[i].c={rd()%n,rd()%(n-l[i]+1)};
            REP(j,l[i]) a[ret[i].c.row][ret[i].c.col+j]^=1;
        } else {
            ret[i].d=VERTICAL;
            ret[i].c={rd()%(n-l[i]+1),rd()%n};
            REP(j,l[i]) a[ret[i].c.row+j][ret[i].c.col]^=1;
        }
    }
    //REP(i,k) output(ret[i],l[i]);
    int hoge=0;
    clock_t strt=clock();
    clock_t crrt=clock();
    while(crrt-strt<950000) {
        int tgt=rd()%k;
        op buf=ret[tgt];
        ret[tgt]=newop(ret[tgt],l[tgt]);
        if(buf.d!=ret[tgt].d||buf.c.row!=ret[tgt].c.row||buf.c.col!=ret[tgt].c.col) {
            hoge++;
        }
        crrt=clock();
    }
    REP(i,k) output(ret[i],l[i]);
    /*REP(i,n) {
        REP(j,n) cout<<a[i][j];
        cout<<endl;
    }
    cout<<hoge<<endl;*/
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0