Submission #72942316

---

Source Code Expand

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<sys/time.h>
// #include<atcoder/segtree>
// #include<atcoder/convolution>

using namespace std;

// using mint = atcoder::modint998244353;

inline unsigned int get_rand() {
    static unsigned int y = 2463534242;
    return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
}
inline long long get_usec() {
    timeval tv;
    gettimeofday(&tv, NULL);
    return (long long)tv.tv_sec * 1000000 + tv.tv_usec;
}
template <class T>
void shuffle(vector<T>& a) {
    for (int i = (int)a.size() - 1; i > 0; --i) {
        int j = get_rand() % (i + 1);
        swap(a[i], a[j]);
    }
}


using P = pair<int, int>;
const int M = 998244353;
const long long LM = 1LL << 60;

long long start_usec;


pair<int, vector<int>> solve(const vector<vector<int>>& edge, int k, int T) {
    int n = edge.size();
    vector<int> thresh(n, M);
    vector<bool> painted(n);
    for (int i = k; i < n; ++i) {
        thresh[i] = get_rand() % T;
    }
    vector<int> vis_count(n);
    auto get_random_route = [&](int p, int prv, int lim) {
        vector<int> res;
        while (true) {
            int nx = edge[p][get_rand() % edge[p].size()];
            while (nx == prv) {
                nx = edge[p][get_rand() % edge[p].size()];
            }
            res.push_back(nx);
            prv = p;
            p = nx;
            if (p < k) {
                break;
            }
            if ((int)res.size() >= lim) {
                return vector<int>();
            }
        }
        return res;
    };
    auto get_str = [&](const vector<int>& route, int turn) {
        string res = "";
        vector<int> pp;
        for (int i = 0; i < (int)route.size() - 1; ++i) {
            assert(route[i] >= k);
            if (painted[route[i]]) {
                res += 'R';
            }
            else {
                res += 'W';
            }
            if (thresh[route[i]] < turn + i && !painted[route[i]]) {
                painted[route[i]] = true;
                pp.push_back(route[i]);
            }
        }
        for (auto&& i : pp) {
            painted[i] = false;
        }
        return res;
    };
    vector<set<string>> ices(k);
    auto calc_penalty = [&](const vector<int>& route, int turn, bool loose, int best) {
        auto s = get_str(route, turn);
        int dst = route.back();
        int res = 0;
        res += route.size();
        if (ices[dst].count(s)) {
            bool ff = false;
            if (loose && res + 10 < best) {
                for (int i = 0; i < (int)s.size() && !ff; ++i) {
                    if (s[i] == 'W') {
                        s[i] = 'R';
                        ff |= !ices[dst].count(s);
                        s[i] = 'W';
                    }
                }
            }
            if (ff) {
                res += 10;
            }
            else {
                res += 1000;
            }
            // res += route.size() / 10;
            // return res;
        }
        return res;
    };
    int p = 0;
    int prv = -1;
    int turn = 0;
    vector<int> commands;
    int cnt = 0;
    int miss = 0;
    while (turn < T) {
        if (get_usec() - start_usec > 1980000) {
            break;
        }
        bool ch = get_rand() % 8 == 0;
        auto route = get_random_route(p, prv, M);
        int pen = calc_penalty(route, turn, ch, M);

        for (int _ = 0; _ < 300; ++_) {
            auto tmp = get_random_route(p, prv, pen);
            if (tmp.empty()) {
                continue;
            }
            int tmppen = calc_penalty(tmp, turn, ch, pen);
            if (pen > tmppen) {
                swap(route, tmp);
                swap(pen, tmppen);
            }
        }
        auto s = get_str(route, turn);
        int dst = route.back();
        // if (false) {
        if (ch && ices[dst].count(s)) {
            vector<int> last_idx(n, -1);
            for (int i = 0; i < (int)commands.size(); ++i) {
                if (commands[i] != -1) {
                    last_idx[commands[i]] = i;
                }
            }
            vector<int> idx;
            for (int i = 0; i < (int)route.size() - 1; ++i) {
                idx.push_back(i);
            }
            // shuffle(idx);
            for (auto&& i : idx) {
                assert(route[i] >= k);
                if (last_idx[route[i]] != -1 && !painted[route[i]]) {
                    painted[route[i]] = true;
                    if (1000 > calc_penalty(route, turn, false, 1000)) {
                        s = get_str(route, turn);
                        commands.insert(commands.begin() + last_idx[route[i]] + 1, -1);
                        break;
                    }
                    painted[route[i]] = false;
                }
            }
        }
        if (!ices[dst].count(s)) {
            ++cnt;
        }
        else {
            ++miss;
        }
        ices[dst].insert(s);
        // vector<int> last_idx(n, -1);
        // for (int i = 0; i < (int)route.size(); ++i) {
        //     last_idx[route[i]] = i;
        // }
        for (int i = 0; i < (int)route.size(); ++i) {
            prv = p;
            p = route[i];
            commands.push_back(p);
            if (!painted[p] && thresh[p] < turn) {
                commands.push_back(-1);
                ++turn;
                painted[p] = true;
            }
            ++turn;
        }
    }
    cerr << miss << '\n';
    if ((int)commands.size() > T) {
        commands.resize(T);
    }
    return { cnt, commands };
}



int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    start_usec = get_usec();
    int n, m, k, T;
    cin >> n >> m >> k >> T;
    vector<vector<int>> edge(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int best_score = -1;
    vector<int> best_commands;
    while (get_usec() - start_usec < 1950000) {
    // for (int _ = 0; _ < 8; ++_) {
        auto r = solve(edge, k, T);
        if (best_score < r.first) {
            best_score = r.first;
            best_commands = r.second;
        }
    }
    cerr << best_score << '\n';
    for (auto&& i : best_commands) {
        cout << i << '\n';
    }



    return 0;
}

Submission Info

Judge Result