huga

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(int argc, char** argv) {
    if (argc != 4) {
        cerr << "arguments" << endl;
        return 0;
    }
    int n = atoi(argv[1]);
    string f1 = argv[2];
    string f2 = argv[3];
    vector<ll> v1(n), v2(n);

    ifstream if1(f1);
    if (if1.fail()) {
        cerr << "f1 error" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) if1 >> v1[i];
    if1.close();
    ifstream if2(f2);
    if (if2.fail()) {
        cerr << "f2 error" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) if2 >> v2[i];
    if2.close();
    double s1 = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
        s1 += v1[i]/(double)max(v1[i], v2[i]);
        s2 += v2[i]/(double)max(v1[i], v2[i]);
    }
    cout << s1 << " " << s2 << endl;

    pair<int,double> si[200];
    for (int i = 0; i < n; i++) {
        ifstream if3("test/" + to_string(i+1) + ".txt");
        if3 >> si[i].first;
        if3.close();
        si[i].second = v1[i] / (double)max(v1[i],v2[i]);
    }

    sort(si, si+n);

    ofstream of1("tmp.txt");
    for (int i = 0; i < n; i++) {
        of1 << si[i].first << " " << si[i].second << endl;
    }
    of1.close();
}

piyo

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(int argc, char** argv) {
    if (argc != 3) {
        cerr << "arguments" << endl;
        return 0;
    }
    int n = atoi(argv[1]);
    string f1 = argv[2];
    vector<ll> v1(n), v2(n);

    ifstream if1(f1);
    if (if1.fail()) {
        cerr << "f1 error" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) if1 >> v1[i];
    if1.close();
    ifstream if2("result/best.txt");
    if (if2.fail()) {
        cerr << "f2 error" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) if2 >> v2[i];
    if2.close();
    for (int i = 0; i < n; i++) {
        v2[i] = max(v1[i], v2[i]);
    }
    ofstream of2("result/best.txt");
    for (int i = 0; i < n; i++) {
        of2 << v2[i] << endl;
    }
    of2.close();
}

puyo

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(int argc, char** argv) {
    if (argc != 3) {
        cerr << "arguments" << endl;
        return 0;
    }
    int n = atoi(argv[1]);
    string f1 = argv[2];
    vector<ll> v1(n), v2(n);

    ifstream if1(f1);
    if (if1.fail()) {
        cerr << "f1 error" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) if1 >> v1[i];
    if1.close();
    ifstream if2("result/best.txt");
    if (if2.fail()) {
        cerr << "f2 error" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) if2 >> v2[i];
    if2.close();
    for (int i = 0; i < n; i++) {
        v2[i] = max(v1[i], v2[i]);
    }
    ofstream of2("result/best.txt");
    for (int i = 0; i < n; i++) {
        of2 << v2[i] << endl;
    }
    of2.close();
}

run

if [ -e result/$1.txt ]; then
    rm result/$1.txt
fi

for i in `seq 1 200`
do
    ./obj/$1 < test/$i.txt > tmp.txt
    ./obj/judge test/$i.txt tmp.txt >> result/$1.txt
done

tco2019_hoge

#pragma GCC optimize ("O3")

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <random>
#include <queue>
#include <string.h>

//#define DEBUG

using namespace std;
typedef long long int ll;
typedef pair<int, int> pi;

const unsigned long long int cycle_per_sec = 2800000000;

unsigned long long int getCycle() {
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}

double getTime (unsigned long long int begin_cycle) {
    return (double)(getCycle() - begin_cycle) / cycle_per_sec;
}

class XorShift {
public:
    unsigned int x;
    unsigned int y;
    unsigned int z;
    unsigned int w;
    unsigned int t;
    
    XorShift(int tmp) {
        mt19937 rnd(tmp);
        x = rnd();
        y = rnd();
        z = rnd();
        w = rnd();
        t = 1;
    }
    
    int rand() {
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return w & 0x7fffffff;
    }
} engine(rand());

inline double exp1(double x) {
    x = 1.0 + x / 16.0;
    x *= x; x *= x; x *= x; x *= x;
    return x;
}

constexpr int INF = 1000000000;
constexpr ll LINF = INF*(ll)INF;
constexpr int MAX_N = 50;
constexpr int B = 52;
constexpr int TILE_N = 6;
constexpr int PENALTY = -1000;
constexpr int dir[4] = {1, B, -1, -B};
/*
constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};
*/
constexpr int POW9[7] = {1, 9, 9*9, 9*9*9, 9*9*9*9, 9*9*9*9*9, 9*9*9*9*9*9};

struct BLOCK {
    int si, score;
    int pos[7];

    void copy(BLOCK& b) {
        si = b.si;
        score = b.score;
        for (int i = 0; i < si; i++) pos[i] = b.pos[i];
    }
};

struct STATE {
    int ans[B*B];
    int tiles[TILE_N];
    ll score;
    int t_id;
    BLOCK blocks[MAX_N*MAX_N];

    void init (int N, int* _tiles) {
        for (int i = 0; i < N+2; i++) {
            for (int j = 0; j < N+2; j++) {
                if (i == 0 || i == N+1 || j == 0 || j == N+1) ans[i*B+j] = INF;
                else ans[i*B+j] = -1;
            }
        }
        for (int i = 0; i < TILE_N; i++) tiles[i] = _tiles[i];
        score = N * N * PENALTY;
        t_id = 1;
    }

    void copy (int N, STATE& st) {
        t_id = st.t_id; score = st.score;
        for (int i = 0; i < TILE_N; i++) tiles[i] = st.tiles[i];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                ans[i*B+j] = st.ans[i*B+j];
            }
        }
        for (int i = 1; i < t_id; i++) blocks[i].copy(st.blocks[i]);
    }

    void compress (int N) {
        int nums[MAX_N*MAX_N], num_cnt = 0;
        int rev[MAX_N*MAX_N];
        bool saw[MAX_N*MAX_N] = {0};
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (ans[i*B+j] == -1) continue;
                if (saw[ans[i*B+j]]) continue;
                saw[ans[i*B+j]] = true;
                nums[num_cnt++] = ans[i*B+j];
            }
        }
        sort(nums, nums+num_cnt);
        for (int i = 0; i < num_cnt; i++) rev[nums[i]] = i+1;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (ans[i*B+j] == -1) continue;
                ans[i*B+j] = rev[ans[i*B+j]];
            }
        }
        t_id = num_cnt+1;
        for (int i = 0; i < num_cnt; i++) {
            if (i+1 == nums[i]) continue;
            blocks[i+1].copy(blocks[nums[i]]);
        }
    }
};

int N;
int grid[B*B]; // edge is undefined
int agrid[B*B]; // edge is undefined
int TILES[TILE_N];
STATE best_state;
STATE sub_state;

void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> grid[i*B+j];
            agrid[i*B+j] = abs(grid[i*B+j]);
        }
    }
    for (int i = 0; i < TILE_N; i++) {
        cin >> TILES[i];
    }
}

void init() {
    best_state.init(N, TILES);
}

void block_search_neo (STATE& state, int t_len, int x, BLOCK& block) {
    block.score = -INF;
    if (state.ans[x] != -1) return;
    int que[10][16];
    int que_en[10] = {0};

    int si = 0;
    int val = grid[x];

    block.pos[si++] = x;
    state.ans[x] = 0;
    for (int u = 0; u < 4; u++) {
        int tx = x + dir[u];
        if (state.ans[tx] != -1) continue;
        int v = agrid[tx];
        que[v][que_en[v]++] = tx;
    }

    while (true) {
        int nxt = -1;
        for (int u = 9; u >= 0; u--) {
            bool ok = false;
            while (que_en[u]) {
                nxt = que[u][--que_en[u]];
                if (state.ans[nxt] == -1 && (engine.rand()&7)) {
                    ok = true;
                    break;
                }
            }
            if (ok) break;
            else nxt = -1;
        }
        if (nxt== -1) break;
        val *= grid[nxt];
        block.pos[si++] = nxt;
        state.ans[nxt] = 0;
        if (si == t_len) break;

        int tx = nxt + dir[0];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
        tx = nxt + dir[1];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
        tx = nxt + dir[2];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
        tx = nxt + dir[3];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
    }
    for (int u = 0; u < si; u++) state.ans[block.pos[u]] = -1;
    if (si == t_len && val > block.score) {
        block.score = val;
        block.si = t_len;
    }
}


void block_search (STATE& state, int t_len, int x, BLOCK& block) {
    block.score = -INF;
    if (state.ans[x] != -1) return;
    int que[10][24];
    int que_en[10] = {0};

    int si = 0;
    int val = 1;

    {
        val *= grid[x];
        block.pos[si++] = x;
        state.ans[x] = 0;
        for (int u = 0; u < 4; u++) {
            int tx = x + dir[u];
            if (state.ans[tx] != -1) continue;
            //int v = abs(grid[tx]);
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
    }

    while (true) {
        int nxt = -1;
        for (int u = 9; u >= 0; u--) {
            bool ok = false;
            while (que_en[u]) {
                nxt = que[u][--que_en[u]];
                if (state.ans[nxt] != -1) continue;
                if (engine.rand()%10 <= 0) continue;
                ok = true;
                break;
            }
            if (ok) break;
            else nxt = -1;
        }
        if (nxt== -1) break;
        val *= grid[nxt];
        block.pos[si++] = nxt;
        state.ans[nxt] = 0;
        if (si == t_len) break;

        int tx = nxt + dir[0];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
        tx = nxt + dir[1];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
        tx = nxt + dir[2];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
        tx = nxt + dir[3];
        if (state.ans[tx] == -1) {
            int v = agrid[tx];
            que[v][que_en[v]++] = tx;
        }
    }
    for (int u = 0; u < si; u++) state.ans[block.pos[u]] = -1;
    if (si == t_len && val > block.score) {
        block.score = val;
        block.si = t_len;
    }
}

void fill_block_search (STATE& state, int t_len, int x, BLOCK& block) {
    block.score = -INF;
    if (state.ans[x] != -1) return;
    int que[30];
    int que_en = 0;

    int si = 0;
    int val = 1;
    int new_pos[7];
    que[que_en++] = x;

    while (que_en) {
        int ind = engine.rand()%que_en;
        int nxt = que[ind];
        while (state.ans[nxt] != -1) {
            for (int i = ind+1; i < que_en; i++) {
                que[i-1] = que[i];
            }
            que_en--;
            if (!que_en) {
                nxt= -1;
                break;
            }
            ind = engine.rand()%que_en;
            nxt = que[ind];
        }
        if (nxt== -1) break;
        for (int i = ind+1; i < que_en; i++) {
            que[i-1] = que[i];
        }
        que_en--;

        val *= grid[nxt];
        new_pos[si++] = nxt;
        state.ans[nxt] = 0;
        if (si == t_len) break;
        for (int u = 0; u < 4; u++) {
            int tx = nxt + dir[u];
            if (state.ans[tx] != -1) continue;
            que[que_en++] = tx;
        }
    }
    for (int u = 0; u < si; u++) state.ans[new_pos[u]] = -1;
    if (si == t_len) {
        block.score = val;
        block.si = t_len;
        for (int u = 0; u < t_len; u++) block.pos[u] = new_pos[u];
    }
}

void greedy (STATE& state, int i) {
    int& t_id = state.t_id;

    BLOCK block[B*B];

    for (int j = 1; j <= N; j++) {
        for (int k = 1; k <= N; k++) {
            block[j*B+k].score = -INF;
        }
    }
    int t_len = i+2;

    for (int _ = 0; _ < 10; _++) {
        for (int j = N; j >= 1; j--) {
            for (int k = N; k >= 1; k--){
                if (state.ans[j*B+k] != -1) continue;
                BLOCK new_block;
                block_search(state, t_len, j*B+k, new_block);
                if (new_block.score > block[j*B+k].score) {
                    block[j*B+k].copy(new_block);
                }
            }
        }
    }

    while (state.tiles[i]) {
        int score = -INF;
        int best_p = 0;
        int pos[7];
        for (int j = N; j >= 1; j--) {
            for (int k = N; k >= 1; k--){
                if (state.ans[j*B+k] != -1) continue;
                if (block[j*B+k].score > score) {
                    score = block[j*B+k].score;
                    best_p = j*B+k;
                }
            }
        }
        if (score <= -INF) break;
        for (int u = 0; u < t_len; u++) pos[u] = block[best_p].pos[u];
        state.score += t_len * 1000 + score;
        state.tiles[i]--;
        for (int j = 0; j < t_len; j++) {
            state.ans[pos[j]] = t_id;
        }
        state.blocks[t_id++].copy(block[best_p]);

        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                int x = j*B+k;
                if (block[x].score == -INF) continue;
                bool del = false;
                for (int u = 0; u < t_len; u++) {
                    if (state.ans[block[x].pos[u]] != -1) {
                        block[x].score = -INF;
                        del = true;
                        break;
                    }
                }
                if (del) {
                    for (int _ = 0; _ < 10; _++) {
                        BLOCK new_block;
                        block_search(state, t_len, x, new_block);
                        if (new_block.score > block[x].score) {
                            block[x].copy(new_block);
                        }
                    }
                }
            }
        }
    }
}

ll calc_state_score (STATE& state) {
    int que[1000];
    bool saw[10000] = {0};
    ll ret = PENALTY*N*N;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int x = i*B+j;
            if (state.ans[x] == -1) continue;
            if (saw[state.ans[x]]) continue;
            saw[state.ans[x]] = true;

            int id = state.ans[x];
            int que_st = 0, que_en = 0;
            int pos[7];
            int si = 0;
            int val = 1;
            que[que_en++] = x;
            while (que_en != que_st) {
                int p = que[que_st++];
                if (state.ans[p] != id) continue;
                pos[si++] = p;
                state.ans[p] = INF;
                val *= grid[p];
                for (int u = 0; u < 4; u++) {
                    que[que_en++] = p+dir[u];
                }
            }
            for (int k = 0; k < si; k++) state.ans[pos[k]] = id;
            ret += val-si*PENALTY;
        }
    }
    return ret;
}

void recalc_block_state (STATE& state) {
    int que[1000];
    bool saw[10000] = {0};
    ll ret = PENALTY*N*N;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int x = i*B+j;
            if (state.ans[x] == -1) continue;
            if (saw[state.ans[x]]) continue;
            saw[state.ans[x]] = true;

            int id = state.ans[x];
            int que_en = 0;
            BLOCK now_block;
            now_block.si = 0; now_block.score = 1;
            que[que_en++] = x;
            while (que_en) {
                int p = que[--que_en];
                if (state.ans[p] != id) continue;
                now_block.pos[now_block.si++] = p;
                state.ans[p] = INF;
                now_block.score *= grid[p];
                for (int u = 0; u < 4; u++) {
                    que[que_en++] = p+dir[u];
                }
            }
            for (int k = 0; k < now_block.si; k++) state.ans[now_block.pos[k]] = id;
            state.blocks[id] = now_block;
            ret += now_block.score-now_block.si*PENALTY;
        }
    }
    state.score = ret;
}

bool connect_check (int* pos, int si) {
    bool saw[10] = {0};
    bool con[10][10];
    for (int i = 0; i < si; i++) {
        for (int j = 0; j < si; j++) {
            con[i][j] = 0;
            for (int u = 0; u < 4; u++) {
                if (pos[i]-pos[j] == dir[u]) con[i][j] = 1;
            }
        }
    }
    int que[10];
    int que_st = 0, que_en = 0;
    que[que_en++] = 0;
    saw[0] = true;
    while (que_st != que_en) {
        int p = que[que_st++];
        for (int i = 0; i < si; i++) {
            if (!con[p][i]) continue;
            if (saw[i]) continue;
            que[que_en++] = i;
            saw[i] = true;
        }
    }
    for (int i = 0; i < si; i++) if (!saw[i]) return false;
    return true;
}

void sub_blush_up (STATE& state, int* blanks, int b_si, int* pos, int p_si) {
    for (int i = 0; i < b_si; i++) {
        int blank = blanks[i];
        int c1 = 0;
        for (int u = 0; u < 4; u++) {
            if (state.ans[blank+dir[u]] == -1) c1++;
        }
        for (int j = 0; j < p_si; j++) {
            int p = pos[j];
            int c2 = 0;
            for (int u = 0; u < 4; u++) {
                if (p-blank == dir[u]) c2--;
            }
            for (int u = 0; u < 4; u++) {
                if (state.ans[p+dir[u]] == -1) c2++;
            }
            if (abs(grid[blank]) < abs(grid[p])) continue;
            if (grid[blank]*grid[p] <= 0) continue;
            if (c1 > c2) continue;
            int pres = pos[j];
            pos[j] = blank;
            if (connect_check(pos, p_si)) return;
            pos[j] = pres;
        }
    }
}

void blush_up (STATE& state) {
    bool checked[10000] = {0};
    int que[1000];
    int que_st, que_en;
    int blanks[100];
    int b_si = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int x = i*B+j;
            if (state.ans[x] == -1) continue;
            int id = state.ans[x];
            if (checked[id]) continue;
            checked[id] = true;
            que_st = 0; que_en = 0;
            b_si = 0;
            int pos[7];
            int pre[7];
            int si = 0;
            que[que_en++] = x;
            while (que_en != que_st) {
                int p = que[que_st++];
                if (state.ans[p] == -1) {
                    bool ok = true;
                    for (int k = 0; k < b_si; k++) {
                        if (blanks[k] == p) ok = false;
                    }
                    if (ok) blanks[b_si++] = p;
                }
                if (state.ans[p] != id) continue;
                pre[si] = p;
                pos[si++] = p;
                state.ans[p] = INF;
                for (int u = 0; u < 4; u++) {
                    que[que_en++] = p+dir[u];
                }
            }
            sub_blush_up(state, blanks, b_si, pos, si);

            for (int k = 0; k < si; k++) state.ans[pre[k]] = -1;
            for (int k = 0; k < si; k++) state.ans[pos[k]] = id;
        }
    }
}

void polish_up (STATE& state, double temp) {
    int id = engine.rand()%(state.t_id-1) + 1;

    BLOCK& pre_block = state.blocks[id];
    int si = pre_block.si;
    for (int k = 0; k < si; k++) state.ans[pre_block.pos[k]] = -1;

    BLOCK block;
    block.score = -INF;
    if (engine.rand()%10) {
        int k = engine.rand()%si;
        state.ans[pre_block.pos[k]] = INF;

        int v = engine.rand()%si;
        while (v == k) v = engine.rand()%si;
        block_search_neo(state, si, pre_block.pos[v], block);

        state.ans[pre_block.pos[k]] = -1;
    } else {
        int x1 = engine.rand()%N+1, y1 = engine.rand()%N+1;
        while (state.ans[x1*B+y1] != -1 || grid[x1*B+y1] == 0) {
            x1 = engine.rand()%N+1;
            y1 = engine.rand()%N+1;
        }
        block_search_neo(state, si, x1*B+y1, block);
    }

    double prob = (block.score>pre_block.score?1.0:(1.0/exp1((-block.score+pre_block.score)/temp)));

    if (block.score != -INF && prob > (engine.rand()%INF)/(double)INF) {
        for (int k = 0; k < si; k++) state.ans[block.pos[k]] = id;
        state.score = state.score+block.score-pre_block.score;
        pre_block.copy(block);
    } else {
        for (int k = 0; k < si; k++) state.ans[pre_block.pos[k]] = id;
    }
}

void fit_size (STATE& state, int x, int s, bool first_4) {
    if (first_4) {
        if (state.ans[x] != -1) return;
        int cnt = 0;
        for (int u = 0; u < 4; u++) {
            int tx = x+dir[u];
            if (state.ans[tx] == 1) cnt++;
        }
        if (cnt != 3) return;
    }
    int pos[10];
    int si = 0, val = 1;
    int que[1000];
    int que_st = 0, que_en = 0;
    que[que_en++] = x;
    while (que_en > que_st) {
        int q = que[que_st++];
        if (state.ans[q] != -1) continue;
        state.ans[q] = state.t_id;
        val *= grid[q];
        pos[si++] = q;
        if (si > s) {
            for (int i = 0; i < si; i++) {
                state.ans[pos[i]] = -1;
            }
            return;
        }
        for (int u = 0; u < 4; u++) {
            que[que_en++] = q+dir[u];
        }
    }
    if (si < s) {
        for (int i = 0; i < si; i++) {
            state.ans[pos[i]] = -1;
        }
        return;
    }
    state.blocks[state.t_id].si = s;
    state.blocks[state.t_id].score = val;
    state.score += -2*PENALTY + val;
    state.t_id++;
    state.tiles[s-2]--;
}

void put_holeless (STATE& state, int x, int s) {
    int pos[10];
    int si = 0, val = 1;
    int que[1000];
    int que_st = 0, que_en = 0;
    bool ok = true;
    que[que_en++] = x;
    while (que_en > que_st) {
        int q = que[que_st++];
        if (state.ans[q] != -1) continue;
        state.ans[q] = state.t_id;
        val *= grid[q];
        pos[si++] = q;
        for (int u = 0; u < 4; u++) {
            if (state.ans[q+dir[u]] != -1) continue;
            int np = q+dir[u];
            que[que_en++] = np;
            int cnt = 0;
            for (int v = 0; v < 4; v++) {
                int tx = np+dir[v];
                if (state.ans[tx] != -1) cnt++;
            }
            if (cnt == 4) {
                if (si == s) {
                    ok = false;
                    break;
                }
                state.ans[np] = state.t_id;
                val *= grid[np];
                pos[si++] = np;
            }
        }
        if (si == s) {
            break;
        }
    }
    while (que_en > que_st) {
        int q = que[que_st++];
        if (state.ans[q] != -1) continue;
        int cnt = 0;
        for (int u = 0; u < 4; u++) {
            int tx = q + dir[u];
            if (state.ans[tx] != -1) cnt++;
        }
        if (cnt == 4) {
            ok = false;
            break;
        }
    }
    if (!ok || si < s) {
        for (int i = 0; i < si; i++) {
            state.ans[pos[i]] = -1;
        }
        return;
    }
    state.blocks[state.t_id].si = s;
    state.blocks[state.t_id].score = val;
    state.score += -2*PENALTY + val;
    state.t_id++;
    state.tiles[s-2]--;
}

void put_anyway (STATE& state, int x, int s) {
    int pos[10];
    int si = 0, val = 1;
    int que[1000];
    int que_st = 0, que_en = 0;
    que[que_en++] = x;
    while (que_en > que_st) {
        int q = que[que_st++];
        if (state.ans[q] != -1) continue;
        state.ans[q] = state.t_id;
        val *= grid[q];
        pos[si++] = q;
        if (si == s) {
            break;
        }
        for (int u = 0; u < 4; u++) {
            que[que_en++] = q+dir[u];
        }
    }
    if (si < s) {
        for (int i = 0; i < si; i++) {
            state.ans[pos[i]] = -1;
        }
        return;
    }
    state.blocks[state.t_id].si = s;
    state.blocks[state.t_id].score = val;
    for (int i = 0; i < si; i++) state.blocks[state.t_id].pos[i] = pos[i];
    state.score += -2*PENALTY + val;
    state.t_id++;
    state.tiles[s-2]--;
}

bool erase_one_block(STATE& state) {
    int x1 = engine.rand()%N+1;
    int x2 = engine.rand()%N+1;
    for (int _ = 0; _ < N*N; _++) {
        if (state.ans[x1*B+x2] == -1) break;
        x1 = engine.rand()%N+1;
        x2 = engine.rand()%N+1;
    }
    if (state.ans[x1*B+x2] != -1) return false;
    int x = x1*B+x2;

    int d = engine.rand()%4;
    int tx = x + dir[d];
    if (state.ans[tx] == -1 || state.ans[tx] == INF) return false;
    int id = state.ans[tx];
    int& sz = state.blocks[id].si;
    if (sz > 5) return false;
    if (sz == 5 && state.blocks[id].score > 2000) return false;

    for (int i = 0; i < state.blocks[id].si; i++) {
        int p = state.blocks[id].pos[i];
        state.ans[p] = -1;
    }
    state.tiles[sz-2]++;

    int score_dif = sz*PENALTY - state.blocks[id].score;

    BLOCK nxt_blocks[10];
    int nxt_bsize = 0;

    for (int __ = 0; __ < 10; __++) {
        int len = engine.rand()%4+2;
        for (int _ = 0; _ < 10; _++) {
            if (state.tiles[len-2] != 0) break;
        }
        if (state.tiles[len-2] == 0) break;
        int n_p = state.blocks[id].pos[engine.rand()%sz];
        for (int _ = 0; _ < 10; _++) {
            if (state.ans[n_p] == -1) break;
            state.blocks[id].pos[engine.rand()%sz];
        }
        if (state.ans[n_p] != -1) break;

        fill_block_search(state, len, n_p, nxt_blocks[nxt_bsize]);
        if (nxt_blocks[nxt_bsize].score == -INF) continue;
        for (int i = 0; i < nxt_blocks[nxt_bsize].si; i++) {
            int p = nxt_blocks[nxt_bsize].pos[i];
            state.ans[p] = INF;
        }
        state.tiles[len-2]--;
        score_dif += -1*len*PENALTY + nxt_blocks[nxt_bsize].score;
        nxt_bsize++;
    }
    for (int i = 0; i < nxt_bsize; i++) {
        for (int j = 0; j < nxt_blocks[i].si; j++) {
            int p = nxt_blocks[i].pos[j];
            state.ans[p] = -1;
        }
        state.tiles[nxt_blocks[i].si-2]++;
    }

    if (score_dif < 0) { //fail
        for (int i = 0; i < state.blocks[id].si; i++) {
            int p = state.blocks[id].pos[i];
            state.ans[p] = id;
        }
        state.tiles[sz-2]--;
    } else {
        for (int i = 0; i < nxt_bsize; i++) {
            for (int j = 0; j < nxt_blocks[i].si; j++) {
                int p = nxt_blocks[i].pos[j];
                state.ans[p] = state.t_id;
            }
            state.tiles[nxt_blocks[i].si-2]--;
            state.blocks[state.t_id].copy(nxt_blocks[i]);
            state.t_id++;
            state.score += score_dif;
        }
    }
    return true;
}

void merge_two_block(STATE& state) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int x = i*B+j;
            if (state.ans[x] == -1) continue;
            if (state.tiles[2] == 0) break;
            int id1 = state.ans[x];
            if (state.blocks[id1].si != 2) continue;
            for (int u = 0; u < 4; u++) {
                int tx = x + dir[u];
                if (state.ans[tx] == -1 || state.ans[tx] == INF) continue;
                int id = state.ans[tx];
                if (id == id1) continue;
                int& sz = state.blocks[id].si;
                if (sz != 2) continue;
                for (int v = 0; v < 4; v++) {
                    int sx = tx + dir[v];
                    if (state.ans[sx] != id) continue;
                    state.ans[sx] = id1;
                    break;
                }
                state.ans[tx] = id1;
                state.tiles[0] += 2;
                state.tiles[2]--;
                state.blocks[id1].si = 4;
                break;
            }
        }
    }
}

void merge_twothree_block(STATE& state, int thres) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int x = i*B+j;
            if (state.ans[x] == -1) continue;
            if (state.tiles[3] == 0) break;
            int id1 = state.ans[x];
            if (state.blocks[id1].si != 2) continue;
            int val = grid[x];
            for (int u = 0; u < 4; u++) {
                if (state.ans[x+dir[u]] == id1) val *= grid[x+dir[u]];
            }
            for (int u = 0; u < 4; u++) {
                int tx = x + dir[u];
                if (state.ans[tx] == -1 || state.ans[tx] == INF) continue;
                int id = state.ans[tx];
                if (id == id1) continue;
                int& sz = state.blocks[id].si;
                if (sz != 3) continue;
                int nval = val * grid[tx];
                for (int v = 0; v < 4; v++) {
                    int sx = tx + dir[v];
                    if (state.ans[sx] != id) continue;
                    nval *= grid[sx];
                    for (int w = 0; w < 4; w++) {
                        int wx = sx + dir[w];
                        if (wx == tx || state.ans[wx] != id) continue;
                        nval *= grid[wx];
                    }
                }
                if (nval < thres) continue;

                for (int v = 0; v < 4; v++) {
                    int sx = tx + dir[v];
                    if (state.ans[sx] != id) continue;
                    state.ans[sx] = id1;
                    for (int w = 0; w < 4; w++) {
                        int wx = sx + dir[w];
                        if (wx == tx || state.ans[wx] != id) continue;
                        state.ans[wx] = id1;
                    }
                }
                state.ans[tx] = id1;
                state.tiles[0]++;
                state.tiles[1]++;
                state.tiles[3]--;
                state.blocks[id1].si = 5;
                break;
            }
        }
    }
}

void last_solve (STATE& state, unsigned long long int start_cycle) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int si = 2; si <= 4; si++) {
                if (state.tiles[si-2] == 0) break;
                if (si == 4) fit_size(state, i*B+j, si, true);
                fit_size(state, i*B+j, si, false);
            }
        }
    }
    for (int i = 4; i >= 2; i--) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (state.ans[j*B+k] != -1) continue;
                if (state.tiles[i-2] == 0) break;
                put_holeless(state, j*B+k, i);
            }
        }
    }
    while (getTime(start_cycle) < 9.7) {
        for (int i = 4; i >= 2; i--) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    if (state.ans[j*B+k] != -1) continue;
                    if (state.tiles[i-2] == 0) break;
                    put_anyway(state, j*B+k, i);
                }
            }
        }
        merge_two_block(state);

        recalc_block_state(state);

        for (int _ = 0; _ < N*N; _++) {
            if (erase_one_block(state)) {
                break;
            }
        }
        state.compress(N);
    }
    while (getTime(start_cycle) < 9.75) {
        for (int i = 4; i >= 2; i--) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    if (state.ans[j*B+k] != -1) continue;
                    if (state.tiles[i-2] == 0) break;
                    put_anyway(state, j*B+k, i);
                }
            }
        }
        merge_twothree_block(state, 0);

        recalc_block_state(state);

        for (int _ = 0; _ < N*N; _++) {
            if (erase_one_block(state)) {
                break;
            }
        }
        state.compress(N);
    }
}

void solve() {
    unsigned long long int start_cycle = getCycle();
    //double time_span[4] = {5.0, 7.5, 8.5, 9.0};
    //double time_span[3] = {7.7, 8.7, 9.2};
    double time_len[3] = {7.7, 1.0, 0.5};
    int span_cnt[3] = {0};
    best_state.init(N, TILES);

    for (int i = 5; i >= 3; i--) {
        greedy(best_state, i);
        if (best_state.t_id == 1) continue;
        int DIV = 5 + MAX_N*MAX_N/(N*N*2);
        int st_dif = 1, en_dif = 1;
        for (int j = 0; j < i; j++) st_dif *= 10;
        en_dif = st_dif/10;
        //en_dif = st_dif/10;
        for (int j = 0; j < DIV; j++) {
            sub_state.copy(N, best_state);
            double pre_t = getTime(start_cycle);
            double now_t = pre_t;
            double end_t = pre_t + time_len[5-i]/DIV;
            while (true) {
                if (span_cnt[5-i]%1000 == 0) {
                    now_t = getTime(start_cycle);
                    if (now_t > end_t) break;
                }
                span_cnt[5-i]++;
                double temp = st_dif + (en_dif-st_dif) * (now_t-pre_t) / (end_t-pre_t);
                polish_up(sub_state, temp);
            }
            if (sub_state.score > best_state.score) best_state.copy(N, sub_state);
        }
    }
    for (int _ = 0; _ < 10; _++) blush_up(best_state);
#ifdef DEBUG
    cerr << "pre: " << best_state.score << endl;
#endif
    last_solve(best_state, start_cycle);

#ifdef DEBUG
    for (int i = 0; i < 3; i++) cerr << span_cnt[i] << " ";
    cerr << endl;
    for (int i = 0; i < TILE_N; i++) cerr << best_state.tiles[i] << " ";
    cerr << endl;
    cerr << best_state.score << endl;
#endif 
}

void output() {
    cout << N * N << endl;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << best_state.ans[i*B+j] << endl;
        }
    }
}

int main() {
    input();
    init();
    solve();
    output();
}

vis

import numpy
import matplotlib.pyplot as plt

file = open("tmp.txt", "r")

lines = [list(map(float,l.split())) for l in file.readlines()]

plt.plot([l[0] for l in lines], [l[1] for l in lines])
plt.show()