結果

問題 No.5002 stick xor
ユーザー ats5515
提出日時 2018-06-01 21:33:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 989 ms / 1,000 ms
コード長 10,594 bytes
コンパイル時間 34,627 ms
実行使用メモリ 2,152 KB
スコア 52,625
最終ジャッジ日時 2018-06-01 21:33:50
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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

// C++11
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <assert.h>
#include <fstream>
#include <iomanip>
using namespace std;
const int64_t CYCLES_PER_SEC = 2600000000;
const int N = 60;
const int K = 500;
struct Timer {
    int64_t start;
    Timer() { reset(); }
    void reset() { start = getCycle(); }
    void plus(double a) { start -= (a * CYCLES_PER_SEC); }
    inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
    inline int64_t getCycle() {
        uint32_t low, high;
        __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
        return ((int64_t)low) | ((int64_t)high << 32);
    }
};
class XorShift {
public:
    unsigned int x, y, z, w;
    double nL[65536];
    XorShift()
    {
        init();
    }
    void init()
    {
        x = 314159265; y = 358979323; z = 846264338; w = 327950288;
        double n = 1 / (double)(2 * 65536);
        for (int i = 0; i < 65536; i++) {
            nL[i] = log(((double)i / 65536) + n);
        }
    }
    void seeding(int seed) {
        x = 314159265; y = 358979323; z = 846264338; w = ((long long)327950288 * (seed + 1)) % 1000000007;
        for (int i = 0; i < 1000 + (seed % 1000); i++) {
            next();
        }
    }
    inline unsigned int next()
    {
        unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
    }
    inline double nextLog() {
        return nL[next() & 0xFFFF];
    }
    inline int nextInt(int m)
    {
        return (int)(next() % m);
    }
    int nextInt(int min, int max)
    {
        return min + nextInt(max - min + 1);
    }
    inline double nextDouble()
    {
        return (double)next() / ((long long)1 << 32);
    }
};
//The board is rotated by 90 degrees
enum Orientation {
    VERTICAL,
    HORIZONTAL
};
struct Rectangle {
    int leftX;
    int topY;
    Orientation o;
};
typedef char Grid_t;
struct State {
    Rectangle rects[K];
    Grid_t grid[N][N];
    void init(Grid_t _grid[N][N]) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = _grid[i][j];
            }
        }
    }
    int calcScore() {
        int res = N * N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res -= grid[i][j];
            }
        }
        return res;
    }
    int doPlace(int i, int L) {
        int res = 0;
        if (rects[i].o == VERTICAL) {
            int x = rects[i].leftX;
            for (int y = rects[i].topY; y < rects[i].topY + L; y++) {
                res += grid[x][y];
                grid[x][y] = 1 - grid[x][y];
            }
        }
        else {
            int y = rects[i].topY;
            for (int x = rects[i].leftX; x < rects[i].leftX + L; x++) {
                res += grid[x][y];
                grid[x][y] = 1 - grid[x][y];
            }
        }
        return res * 2 - L;
    }
    int erase(int i, int L) {
        int res = 0;
        if (rects[i].o == VERTICAL) {
            int x = rects[i].leftX;
            for (int y = rects[i].topY; y < rects[i].topY + L; y++) {
                res += grid[x][y];
                grid[x][y] = 1 - grid[x][y];
            }
        }
        else {
            int y = rects[i].topY;
            for (int x = rects[i].leftX; x < rects[i].leftX + L; x++) {
                res += grid[x][y];
                grid[x][y] = 1 - grid[x][y];
            }
        }
        return res * 2 - L;
    }
    int placeGreedy(int i, int L, XorShift &rnd) {
        int ones;
        int mx = -1;
        int rr = -1;
        int l;
        int sc;
        //if (rects[i].o == VERTICAL) {
        for (int x = 0; x < N; x++) {
            ones = 0;
            for (int y = 0; y < L; y++) {
                ones += grid[x][y];
            }
            l = 0;
            while (true) {
                if (rr <= ones) {
                    sc = (ones << 12) + (rnd.next() & 0xFFF);
                    if (mx < sc) {
                        rr = ones;
                        mx = sc;
                        rects[i].leftX = x;
                        rects[i].topY = l;
                        rects[i].o = VERTICAL;
                    }
                }
                if (l + L >= N)break;
                ones += grid[x][l + L];
                ones -= grid[x][l];
                l++;
            }
        }
        /*  }
            else {*/
        for (int y = 0; y < N; y++) {
            ones = 0;
            for (int x = 0; x < L; x++) {
                ones += grid[x][y];
            }
            l = 0;
            while (true) {
                if (rr <= ones) {
                    sc = (ones << 12) + (rnd.next() & 0xFFF);
                    if (mx < sc) {
                        mx = sc;
                        rr = ones;
                        rects[i].leftX = l;
                        rects[i].topY = y;
                        rects[i].o = HORIZONTAL;
                    }
                }
                if (l + L >= N)break;
                ones += grid[l + L][y];
                ones -= grid[l][y];
                l++;
            }
        }
        //}
        return doPlace(i, L);
    }
    
};
class Solver {
public:
    XorShift rnd;
    Timer timer;
    //////TASK///////
    Grid_t grid[N][N];
    int L[K];
    int L_sorted[K];
    int h[27];
    int W0;
    /////////////////
    State state;
    void inputFromStdin() {
        int _;
        cin >> _ >> _;
        for (int i = 0; i < K; i++) {
            cin >> L[i];
        }
        W0 = N * N;
        char a;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> a;
                grid[i][j] = a - '0';
                W0 -= grid[i][j];
            }
        }
    }
    void generateTestCase(int seed) {
        XorShift gen;
        gen.seeding(seed);
        for (int i = 0; i < K; i++) {
            L[i] = gen.nextInt(25) + 1;
        }
        sort(L, L + K, greater<int>());
        W0 = N * N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = gen.nextInt(2);
                W0 -= grid[i][j];
            }
        }
        ofstream ofs("input.txt");
        ofs << N << " " << K << endl;
        for (int i = 0; i < K; i++) {
            if (i > 0)ofs << " ";
            ofs << L[i];
        }
        ofs << endl;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ofs << (int)grid[i][j];
            }
            ofs << endl;
        }
    }
    void outputResult() {
        int head[25];
        for (int i = 0; i < K; i++) {
            if (i == 0 || L_sorted[i] > L_sorted[i - 1]) {
                head[L_sorted[i] - 1] = i;
            }
        }
        for (int i = 0; i < K; i++) {
            Rectangle &r = state.rects[head[L[i] - 1]];
            if (r.o == VERTICAL) {
                cout << r.leftX + 1 << " " << r.topY + 1 << " " << r.leftX + 1 << " " << r.topY + L[i] << endl;
            }
            else {
                cout << r.leftX + 1 << " " << r.topY + 1 << " " << r.leftX + L[i] << " " << r.topY + 1 << endl;
            }
            head[L[i] - 1]++;
        }
    }
    void outputDebugInfo() {
        int W1 = state.calcScore();
        cerr << "W0 = " << W0 << ", W1 = " << W1 << endl;
        cerr << "score = " << W1 - W0 << endl;
    }
    int getScore() {
        int W1 = state.calcScore();
        return W1 - W0;
    }
    void init() {
        state.init(grid);
        for (int i = 0; i < K; i++) {
            L_sorted[i] = L[i];
        }
        sort(L_sorted, L_sorted + K);
        h[0] = 0;
        for (int i = 0; i < K; i++) {
            if (i == 0 || L_sorted[i] > L_sorted[i - 1]) {
                h[L_sorted[i]] = i;
            }
        }
        h[26] = K;
    }
    void SA(double timelimit) {
        int score = state.calcScore();
        /*for (int i = K - 1; i >= 0; i--) {
            score += state.placeGreedy(i, L_sorted[i], rnd);
        }*/
        /*for (int i = 0; i < K; i++) {
        score += state.placeGreedy(i, L_sorted[i], rnd);
        }*/
        double ti;
        int a;
        int o;
        int cnt = 0;
        cerr << score << endl;
        cerr << state.calcScore() << endl;
        a = K - 1;
        double st = timer.get();
        cerr << "st=" << st << endl;
        double di = st;
        double dd = (timelimit - st) * 0.1;
        double rem;
        Rectangle tmp;
        double T;
        double T0 = 0.8;
        int bscore;
        int br = 500;
        int rr;
        int mnL = K;
        int xa;
        int ya;
        int xb;
        int yb;
        int la;
        int b;
        int lb;
        Rectangle ba, bb;
        while (true) {
            if ((cnt & 0x3FF) == 0) {
                ti = timer.get();
                if (ti > timelimit) {
                    break;
                }
                rem = (timelimit - ti) / (timelimit - st);
                if (rem > 0) {
                    //rr = 350 * rem;
                    rr = 350 * rem*rem;
                    if (rr < br) {
                        for (int i = br - 1; i >= rr; i--) {
                            score += state.placeGreedy(i, L_sorted[i], rnd);
                        }
                        br = rr;
                        mnL = min(mnL, rr);
                    }
                }
                T = T0 * rem;
                if (di < ti) {
                    di += dd;
                    cerr << score << "  " << rr << endl;
                }
            }
            cnt++;
            bscore = score;
            if (rnd.nextDouble() < 0.0015) {
                a = rnd.nextInt(rr, K - 1);
                score += state.erase(a, L_sorted[a]);
                score += state.placeGreedy(a, L_sorted[a], rnd);
            }
            else {
                
                a = rnd.nextInt(rr, h[25] - 1);
                la = L_sorted[a];
                ba = state.rects[a];
                if (state.rects[a].o == VERTICAL) {
                    if (cnt & 1) {
                        if (state.rects[a].topY > 0) {
                            score += 2 * state.grid[state.rects[a].leftX][state.rects[a].topY - 1] - 1;
                            state.rects[a].topY--;
                            xa = state.rects[a].leftX;
                            ya = state.rects[a].topY;
                            state.grid[xa][ya] ^= 1;
                        }
                        else {
                            continue;
                        }
                    }
                    else {
                        if (state.rects[a].topY + la < N) {
                            score += 2 * state.grid[state.rects[a].leftX][state.rects[a].topY + la] - 1;
                            xa = state.rects[a].leftX;
                            ya = state.rects[a].topY + la;
                            state.grid[xa][ya] ^= 1;
                        }
                        else {
                            continue;
                        }
                    }
                }
                else {
                    if (cnt & 1) {
                        if (state.rects[a].leftX > 0) {
                            score += 2 * state.grid[state.rects[a].leftX - 1][state.rects[a].topY] - 1;
                            state.rects[a].leftX--;
                            xa = state.rects[a].leftX;
                            ya = state.rects[a].topY;
                            state.grid[xa][ya] ^= 1;
                        }
                        else {
                            continue;
                        }
                    }
                    else {
                        if (state.rects[a].leftX + la < N) {
                            score += 2 * state.grid[state.rects[a].leftX + la][state.rects[a].topY] - 1;
                            xa = state.rects[a].leftX + la;
                            ya = state.rects[a].topY;
                            state.grid[xa][ya] ^= 1;
                        }
                        else {
                            continue;
                        }
                    }
                }
                b = rnd.nextInt(h[la + 1], h[la + 2] - 1);
                bb = state.rects[b];
                lb = L_sorted[b];
                //if (lb != la + 1)assert(false);
                if (state.rects[b].o == VERTICAL) {
                    if (cnt & 1) {
                        score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY] - 1;
                        xb = state.rects[b].leftX;
                        yb = state.rects[b].topY;
                        state.rects[b].topY++;
                    }
                    else {
                        score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY + lb - 1] - 1;
                        xb = state.rects[b].leftX;
                        yb = state.rects[b].topY + lb - 1;
                    }
                }
                else {
                    if (cnt & 1) {
                        score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY] - 1;
                        xb = state.rects[b].leftX;
                        yb = state.rects[b].topY;
                        state.rects[b].leftX++;
                    }
                    else {
                        score += 2 * state.grid[state.rects[b].leftX + lb - 1][state.rects[b].topY] - 1;
                        xb = state.rects[b].leftX + lb - 1;
                        yb = state.rects[b].topY;
                    }
                }
                if (score - bscore > T*rnd.nextLog()) {
                    swap(state.rects[a], state.rects[b]);
                    state.grid[xb][yb] ^= 1;
                    //cerr << "ok" << endl;
                }
                else {
                    score = bscore;
                    state.rects[a] = ba;
                    state.rects[b] = bb;
                    state.grid[xa][ya] ^= 1;
                }
            }
        }
        cerr << score << endl;
        cerr << "cnt = " << cnt << endl;
    }
    void solve() {
        init();
        SA(0.98);
        outputDebugInfo();
    }
};
//#define Batch
#ifdef Batch
int main() {
    ofstream ofs("result.csv");
    for (int seed = 0; seed < 30; seed++) {
        Solver solver;
        solver.generateTestCase(seed);
        solver.solve();
        ofs << seed << "," << solver.getScore() << endl;
    }
}
#else
int main() {
    Solver solver;
    //solver.generateTestCase(10);
    solver.inputFromStdin();
    solver.solve();
    solver.outputResult();
}
#endif // Batch
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1