提出 #73752485

---

ソースコード 拡げる

double TL = 1.95;
//#pragma GCC optimize("O3,Ofast,omit-frame-pointer,unroll-all-loops,tree-loop-vectorize,tree-slp-vectorize")
#include <bits/stdc++.h>

const int P5 = 23;

int STANDARD = 1;
using namespace std;
#define F0(i,n) for (int i=0; i<n; i++)
#define F1(i,n) for (int i=1; i<=n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const int inf = 1000000000;
const double pi = acos(-1.0);
typedef pair<int, int> pii;
typedef long long ll;
const double EPS = 1e-9;
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<class A, class B, class C>
ostream& operator<<(ostream& os, const tuple<A, B, C>& p) { os << "(" << get<0>(p) << "," << get<1>(p) << "," << get<2>(p) << ")"; return os; }
istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; }
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& v) {
    os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}"; return os;
}
template<class T, class R>
ostream& operator<<(ostream& os, const map<T,R>& v) {
    os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}"; return os;
}
void print_all() { cerr << endl; }
template <typename H, typename... T>
void print_all(H head, T... tail) { cerr << " " << head; print_all(tail...); }
#ifdef LOCAL
#define PR(...) cerr << #__VA_ARGS__ << " =", print_all(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-all-loops")
#define PR(...)
#endif

chrono::system_clock::time_point init_time = chrono::system_clock::now();
inline double GetSeconds() {
     chrono::system_clock::time_point current_time = chrono::system_clock::now();
     double ret = chrono::duration_cast<std::chrono::nanoseconds>(current_time - init_time).count();
     return ret * 1e-9;
}

const int MAX_RAND = 1 << 30;
struct Rand {
    ll x, y, z, w, o;
    Rand() { throw; }
    Rand(ll seed) { reseed(seed); o = 0; }
    inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0;  F0(i, 20) mix(); }
    inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); }
    inline ll rand() { mix(); return x & (MAX_RAND - 1); }
    inline ll zh() { mix(); return x; }
    inline int nextInt(int n) { return rand() % n; }
    inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; }
    inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; }
    inline double nextDouble() { return rand() * 1.0 / MAX_RAND; }
    inline double nextDouble(double L, double R) { return L + (R - L) * nextDouble(); }
    template<class T> auto REL(T& v) { return v[nextInt(SZ(v))]; }
    template<class T> void RS(vector<T>& v) { F1(i, SZ(v)-1) { int j = nextInt(0, i); swap(v[i], v[j]); } }
    int ws_n; vector<double> ws_prob; vector<int> ws_alias;
    inline void PrepareWeightedSample(const vector<double>& p) {
        ws_n = SZ(p); ws_prob.assign(ws_n, 0); ws_alias.assign(ws_n, 0);
        vector<double> sc(ws_n);
        vector<int> small, large;
        double sum = 0; F0(i, ws_n) sum += p[i];
        F0(i, ws_n) {
            sc[i] = p[i]/sum * ws_n; if (sc[i] < 1) small.push_back(i); else large.push_back(i);
        }
        while(!small.empty() && !large.empty()){
            int l = small.back(); small.pop_back();
            int g = large.back(); large.pop_back();
            ws_prob[l] = sc[l]; ws_alias[l] = g;
            sc[g] = sc[g] - (1 - sc[l]);
            if(sc[g] < 1) small.push_back(g); else large.push_back(g);
        }
        for(int g : large){ ws_prob[g]=1; ws_alias[g]=g; }
        for(int l : small){ ws_prob[l]=1; ws_alias[l]=l; }
    }
    inline int WeightedSample() { int i = nextInt(ws_n); return nextDouble() < ws_prob[i] ? i : ws_alias[i]; }
};
Rand my(2027);
double saveTime;
double t_o[20];
ll c_o[20];
void Init() {
    saveTime = GetSeconds();
    F0(i, 20) t_o[i] = 0.0;
    F0(i, 20) c_o[i] = 0;
}
double Elapsed() { return GetSeconds() - saveTime; }
void Report() {
    double tmp = Elapsed();
    cerr << "-------------------------------------" << endl;
    cerr << "Elapsed time: " << tmp << " sec" << endl;
    double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl;
    F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl;
    cerr << "-------------------------------------" << endl;
}
struct AutoTimer {
    int x;
    double t;
    AutoTimer(int x) : x(x) {
        t = Elapsed();
    }
    ~AutoTimer() {
        t_o[x] += Elapsed() - t;
    }
};
#define AT(i) AutoTimer a##i(i)
//#define AT(i)

// CONSTANTS
const int N = 20;
int n, K, V, W, A_count, A_states, A_walls;
ll bscore, score;
const int LOGN = 1 << 16;
double logs[LOGN];

template<class T> T sqr(T x) { return x*x; }

enum { UP, RIGHT, DOWN, LEFT, STAY };
const int DX[]={-1,0,1,0,0};
const int DY[]={0,1,0,-1,0};
const string DS="URDLS";
const string ROT="LFR";
int qx[N*N], qy[N*N], id[N][N];
int ver[N][N], hor[N][N];
int mapping[N][N], bmapping[N][N];
vector<int> commands, bcommands;
vector<int> adj[N*N];
int nx[1024][5], cn;
int d[N*N][N*N], way[N*N][N*N];
int a[N*N];
int c_count, c_states, c_walls;
int v[N*N][4][16], vz;

struct Robot {
    int spos, sdir, m;
    vector<pii> nwall, nfree;
    set<int> cycle;
    void Random(int sm = -1, int tp = -1) {
        spos = my.nextInt(cn);
        sdir = my.nextInt(4);
        //if (sm == 5) sm = 6;
        if (sm != -1) m = sm;
        nwall.resize(m);
        nfree.resize(m);

        if (m == 4) {
            if (tp == -1) {
                F0(i, m) {
                    nfree[i].first = my.nextInt(-1, 1);
                    nfree[i].second = my.nextInt(m);
                    nwall[i].first = my.nextInt(0, 1) * 2 - 1;
                    nwall[i].second = my.nextInt(m);
                }
            } else {
                nfree[0] = {0, 1};
                nfree[1] = {-1, 2};
                nfree[2] = {0, 3};
                nfree[3] = {1, 0};
                nwall[0] = {-1, 2};
                nwall[2] = {-1, 0};
                nwall[1] = {1, 0};
                nwall[3] = {1, 2};
                sort(nwall.begin(), nwall.end());
                F0(x, tp) next_permutation(nwall.begin(), nwall.end());
            }
        } else if (m == 6) {
            nfree = {{0, 1}, {1, 0}, {-1, 3}, {0, 3}, {-1, 5}, {0, 5}};
            nwall = {{-1, 2}, {1, 0}, {-1, 3}, {-1, 4}, {-1, 5}, {-1, 0}};
            if (tp == -1) {
                my.RS(nwall);
                my.RS(nfree);
            }
        } else if (m == 5) {
            if (tp == -1 && 0) {
                F0(i, m) {
                    nfree[i].first = my.nextInt(-1, 1);
                    nfree[i].second = my.nextInt(m);
                    nwall[i].first = my.nextInt(0, 1) * 2 - 1;
                    nwall[i].second = my.nextInt(m);
                }
            } else {
                int rs = 0;
                if (tp == -1) { tp = my.nextInt(P5); rs = 1; }
                if (tp == 0) {
                    nfree = {{0, 1}, {1, 2}, {-1, 0}, {-1, 4}, {0, 4}};
                    nwall = {{-1, 2}, {-1, 0}, {-1, 3}, {-1, 3}, {-1, 2}};
                }

                if (tp == 1) {
                    nfree = {{0, 1}, {-1, 2}, {1, 0}, {1, 4}, {0, 4}};
                    nwall = {{1, 0}, {1, 0}, {1, 3}, {1, 2}, {1, 2}};
                }

                if (tp == 2) {
                    nfree = {{0, 1}, {-1, 2}, {1, 3}, {0, 0}, {1, 0}};
                    nwall = {{1, 2}, {1, 3}, {1, 4}, {1, 0}, {1, 0}};
                }

                if (tp == 3) {
                    nfree = {{0, 1}, {-1, 2}, {0, 3}, {1, 0}, {-1, 3}};
                    nwall = {{-1, 2}, {1, 2}, {-1, 4}, {-1, 0}, {1, 1}};
                }

                if (tp == 4) {
                    nfree = {{0, 1}, {-1, 2}, {0, 2}, {-1, 4}, {0, 4}};
                    nwall = {{-1, 3}, {-1, 4}, {-1, 3}, {1, 0}, {-1, 0}};
                }

                if (tp == 5) {
                    nfree = {{0, 1}, {0, 2}, {1, 3}, {0, 4}, {-1, 1}};
                    nwall = {{-1, 1}, {1, 3}, {-1, 0}, {-1, 3}, {1, 1}};
                }

                if (tp == 6) {
                    nfree = {{0, 1}, {1, 2}, {-1, 3}, {0, 0}, {-1, 0}};
                    nwall = {{-1, 3}, {-1, 4}, {-1, 2}, {-1, 0}, {-1, 1}};
                }

                if (tp == 7) {
                    nfree = {{0, 1}, {-1, 2}, {0, 3}, {1, 0}, {-1, 4}};
                    nwall = {{-1, 0}, {-1, 4}, {1, 0}, {1, 2}, {-1, 2}};
                }

                if (tp == 8) {
                    nfree = {{0, 0}, {1, 3}, {0, 4}, {0, 3}, {1, 0}};
                    nwall = {{1, 1}, {1, 3}, {1, 4}, {1, 2}, {-1, 3}};
                }

                if (tp == 9) {
                    nfree = {{1, 4}, {-1, 3}, {1, 1}, {0, 4}, {0, 2}};
                    nwall = {{1, 4}, {1, 0}, {1, 1}, {-1, 3}, {-1, 1}};
                }

                if (tp == 10) {
                    nfree = {{0, 0}, {-1, 0}, {0, 1}, {1, 4}, {0, 4}};
                    nwall = {{1, 3}, {1, 3}, {1, 2}, {1, 4}, {-1, 2}};
                }

                if (tp == 11) {
                    nfree = {{1, 1}, {0, 2}, {-1, 3}, {0, 0}, {-1, 2}};
                    nwall = {{1, 1}, {-1, 3}, {-1, 1}, {-1, 4}, {-1, 2}};
                }

                if (tp == 12) {
                    nfree = {{1, 3}, {1, 4}, {0, 1}, {0, 3}, {-1, 2}};
                    nwall = {{1, 3}, {1, 4}, {1, 0}, {-1, 2}, {-1, 4}};
                }

                if (tp == 13) {
                    nfree = {{-1, 2}, {-1, 4}, {0, 2}, {0, 0}, {0, 4}};
                    nwall = {{-1, 0}, {-1, 2}, {-1, 1}, {1, 3}, {-1, 3}};
                }

                if (tp == 14) {
                    nfree = {{-1, 3}, {1, 0}, {-1, 4}, {0, 1}, {0, 4}};
                    nwall = {{-1, 2}, {-1, 3}, {-1, 4}, {1, 3}, {-1, 0}};
                }

                if (tp == 15) {
                    nfree = {{0, 3}, {1, 0}, {1, 3}, {0, 4}, {-1, 1}};
                    nwall = {{-1, 0}, {1, 1}, {1, 3}, {1, 0}, {1, 2}};
                }

                if (tp == 16) {
                    nfree = {{0, 1}, {1, 2}, {0, 4}, {1, 3}, {-1, 0}};
                    nwall = {{1, 3}, {1, 0}, {-1, 0}, {-1, 2}, {1, 2}};
                }

                if (tp == 17) {
                    nfree = {{0, 3}, {0, 1}, {0, 2}, {-1, 2}, {-1, 1}};
                    nwall = {{1, 3}, {-1, 0}, {-1, 4}, {1, 1}, {-1, 3}};
                }

                if (tp == 18) {
                    nfree = {{1, 3}, {0, 0}, {-1, 1}, {0, 2}, {-1, 4}};
                    nwall = {{1, 1}, {-1, 4}, {1, 3}, {-1, 1}, {-1, 3}};
                }

                if (tp == 19) {
                    nfree = {{-1, 4}, {0, 0}, {-1, 2}, {1, 1}, {0, 3}};
                    nwall = {{1, 1}, {-1, 4}, {-1, 1}, {1, 4}, {-1, 2}};
                }

                if (tp == 20) {
                    nfree = {{0, 3}, {1, 0}, {1, 1}, {-1, 4}, {0, 1}};
                    nwall = {{1, 2}, {1, 4}, {1, 1}, {-1, 4}, {1, 0}};
                }

                if (tp == 21) {
                    nfree = {{0, 4}, {0, 1}, {-1, 3}, {0, 3}, {-1, 1}};
                    nwall = {{-1, 4}, {-1, 2}, {1, 2}, {-1, 0}, {-1, 3}};
                }

                if (tp == 22) {
                    nfree = {{0, 4}, {-1, 3}, {1, 4}, {0, 2}, {0, 1}};
                    nwall = {{-1, 1}, {-1, 4}, {1, 3}, {1, 4}, {-1, 3}};
                }
                if (rs) {
                    my.RS(nfree);
                    my.RS(nwall);
                }
            }
        }
    }

    void Sim() {
        vz++;
        pair<pii, int> p(pii(spos, sdir), 0);
        while (1) {
            auto p2 = p;
            int pos = p.first.first;
            int dir = p.first.second;
            int s = p.second;
            if (v[pos][dir][s] == vz) break;
            v[pos][dir][s] = vz;
            if (nx[pos][dir] == pos) {
                p2.first.second = (p2.first.second + 4 + nwall[s].first) & 3;
                p2.second = nwall[s].second;
            } else {
                if (nfree[s].first == 0) p2.first.first = nx[pos][dir];
                else p2.first.second = (p2.first.second + 4 + nfree[s].first) & 3;
                p2.second = nfree[s].second;
            }
            p = p2;
        }
        cycle.clear();
        auto sp = p;
        while (1) {
            auto p2 = p;
            int pos = p.first.first;
            int dir = p.first.second;
            int s = p.second;

            cycle.insert(pos);

            if (nx[pos][dir] == pos) {
                p2.first.second = (p2.first.second + 4 + nwall[s].first) & 3;
                p2.second = nwall[s].second;
            } else {
                if (nfree[s].first == 0) p2.first.first = nx[pos][dir];
                else p2.first.second = (p2.first.second + 4 + nfree[s].first) & 3;
                p2.second = nfree[s].second;
            }
            p = p2;
            if (p == sp) break;
        }
    }
    void Print() {
        cout << m << " " << qx[spos] << " " << qy[spos] << " " << DS[sdir] << endl;
        F0(i, m) {
            cout << ROT[nfree[i].first+1] << " " << nfree[i].second << " ";
            cout << ROT[nwall[i].first+1] << " " << nwall[i].second << endl;
        }
    }
};
vector<Robot> bsol, sol;

void BuildGraph() {
    F0(i, cn) adj[i].clear();
    F0(i, cn) F0(dir, 5) nx[i][dir] = i;
    F0(i, cn) {
        if (qx[i] + 1 < n && !hor[qx[i]][qy[i]]) {
            int i2 = id[qx[i] + 1][qy[i]];
            adj[i].push_back(i2);
            adj[i2].push_back(i);
            nx[i][DOWN] = i2;
            nx[i2][UP] = i;
        }
        if (qy[i] + 1 < n && !ver[qx[i]][qy[i]]) {
            int i2 = id[qx[i]][qy[i] + 1];
            adj[i].push_back(i2);
            adj[i2].push_back(i);
            nx[i][RIGHT] = i2;
            nx[i2][LEFT] = i;
        }
    }
}

void Distances() {
    F0(start, cn) {
        vector<int> q;
        q.push_back(start);
        F0(i, cn) d[start][i] = -1;
        d[start][start] = 0;
        F0(qi, SZ(q)) {
            int i = q[qi];
            for (int j : adj[i]) if (d[start][j] == -1) {
                d[start][j] = d[start][i] + 1;
                way[start][j] = i;
                q.push_back(j);
            }
        }
    }
}

void PrepareGrid() {
    int tmp = 0;
    F0(i, n) F0(j, n) {
        id[i][j] = tmp;
        qx[tmp] = i;
        qy[tmp] = j;
        tmp++;
    }
    cn = n*n;

    string s;
    F0(i, n) {
        cin >> s;
        F0(j, n - 1) {
            ver[i][j] = s[j] - '0';
        }
    }
    F0(i, n - 1) {
        cin >> s;
        F0(j, n) {
            hor[i][j] = s[j] - '0';
        }
    }

    BuildGraph();

    Distances();
}

void Prepare() {
    PR(n, A_count, A_states, A_walls);
    PrepareGrid();
    bscore = inf;
    F0(i, LOGN) logs[i] = -log((i+0.5)/LOGN);
}

void UpdateBest() {
    if (score < bscore) {
        bscore = score;
        bsol = sol;
    }
}

void RandRobot() {
    int bv = -1;
    Robot br;
    map<int, int> M;

    F0(i, cn) F0(d, 4) F0(tp, 24) {
        if (i != 0) continue;
        Robot r;
        r.Random(4, tp);
        r.spos = i;
        r.sdir = d;
        r.Sim();
        int av = SZ(r.cycle);
        M[av]++;
        if (av > bv) {
            bv = av;
            br = r;
            if (bv == cn) {
                i = cn;
                d = 4;
                break;
            }
        }
    }

    // solved with 4, or 4+1
    if (bv == cn || (A_count == 0 && bv == cn - 1)) {
        bsol.push_back(br);
        for (int x : br.cycle) a[x] = 1;
        return;
    }

    F0(i, cn) F0(d, 4) F0(tp, P5) {
        if (i != 0) continue;
        Robot r;
        r.Random(5, tp);
        r.spos = i;
        r.sdir = d;
        r.Sim();
        int av = SZ(r.cycle);
        M[av]++;
        if (av > bv) {
            bv = av;
            br = r;
            if (bv == cn) {
                i = cn;
                d = 4;
                tp = 4;
                break;
            }
        }
    }

    // solved with 5
    if (bv == cn) {
        bsol.push_back(br);
        for (int x : br.cycle) a[x] = 1;
        return;
    }

    F0(i, cn) F0(d, 4) F0(tp, 1) {
        if (i != 0) continue;
        Robot r;
        r.Random(6, tp);
        r.spos = i;
        r.sdir = d;
        r.Sim();
        int av = SZ(r.cycle);
        M[av]++;
        if (av > bv) {
            bv = av;
            br = r;
            if (bv == cn) {
                i = cn;
                d = 4;
                tp = 4;
                break;
            }
        }
    }
    if (bv != cn)
    while (1) {
        double ratio = Elapsed() / TL;
        if (ratio > 1.0) break;
        Robot r;
        //r.Random((int)(4 + ratio * 3.0));
        r.Random(6);
        r.Sim();
        int av = SZ(r.cycle);
        M[av]++;
        if (av > bv) {
            bv = av;
            br = r;
            if (bv == cn) break;
        }
    }

    if (bv != cn) throw;

    // solved with 6, but try harder with 5
    while (1) {
        double ratio = Elapsed() / TL;
        if (ratio > 1.0) break;
        Robot r;
        r.Random(5);
        r.Sim();
        int av = SZ(r.cycle);
        M[av]++;
        if (av >= bv) {
            bv = av;
            br = r;
            if (bv == cn) break;
        }
    }

    bsol.push_back(br);
    for (int x : br.cycle) a[x] = 1;
}

#ifdef VIS
#include "vis.h"
#else
void ShowIt(bool f = false) { (void)f; }
#endif

void Solve() {
    my.reseed(time(0));
    Prepare();

    RandRobot();

    c_count = SZ(bsol);
    c_states = 0;
    for (auto& r : bsol) {
        c_states += r.m;
    }
    c_walls = 0;
    F0(i, cn) if (!a[i]) {
        c_count++;
        c_states++;
    }

    ShowIt(1);

    cout << c_count << endl;

    for (Robot& r : bsol) r.Print();
    F0(i, cn) if (!a[i]) {
        cout << 1 << " " << qx[i] << " " << qy[i] << " " << DS[0] << endl;
        cout << "R" << " " << 0 << " " << "R" << " " << 0 << endl;
    }
    F0(i, n) cout << string(n-1, '0') << endl;
    F0(i, n-1) cout << string(n, '0') << endl;

    V = A_count * (c_count - 1) + A_states * c_states + A_walls * c_walls;
    W = A_count * (cn - 1) + A_states * cn;

    PR(V, W);
    ll rscore = 1 + (1e6 * max(0.0, log2(1.0 * W / V)) + 0.5);
    PR(rscore);

    //Report();
}


void ReadInput() {
    cin >> n >> A_count >> A_states >> A_walls;
}

int main(int argc, char* argv[]) {
    Init();

    int seed1 = 0, seed2 = 0;
    if (argc>1) {
        if (argc == 2) {
            seed1 = seed2 = atoi(argv[1]);
        } else {
            seed1 = atoi(argv[1]);
            seed2 = atoi(argv[2]);
        }
        STANDARD=0;
    }

    if (STANDARD) {
        ReadInput();
        Solve();
        return 0;
    }

    for (int seed=seed1; seed<=seed2; seed++) {
        if (seed>=0 && seed<10000) {
            char inp[128];
            sprintf(inp, "in/%04d.txt", seed);
            char outp[128];
            sprintf(outp, "out/%04d.txt", seed);
            ignore = freopen(inp, "r", stdin);
            ignore = freopen(outp, "w", stdout);
            ReadInput();
            Solve();
            cerr << "Seed #" << seed << " ";
            cerr << bscore << endl;
            //cout << "Score would be " << bscore << endl;
        } else {
            // Generate
            throw;
            Rand my(seed);
        }
    }

    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void Solve()':
./Main.cpp:608:8: warning: unused variable 'rscore' [-Wunused-variable]
  608 |     ll rscore = 1 + (1e6 * max(0.0, log2(1.0 * W / V)) + 0.5);
      |        ^~~~~~

ジャッジ結果