oj.uz

Submission #894549

# Submission time Handle Problem Language Result Execution time Memory
894549 2023-12-28T12:29:51 Z vjudge1 The Collection Game (BOI21_swaps) C++17
0 / 100
 3 ms 344 KB 
#include <bits/stdc++.h>
#include "swaps.h"

using namespace std;

mt19937 gen(time(0));

void add(vector<int>& a, vector<pair<vector<int>, vector<int>>>& all){
    int n = (int)a.size();
    int sz = (n + 1) / 2;
    shuffle(a.begin(), a.end(), gen);
    all.push_back({{}, {}});
    for(int i = 0; i < sz; i++) all.back().first.push_back(a[i]);
    for(int i = sz; i < n; i++) all.back().second.push_back(a[i]);
}

void solve(int N, int V) {
    vector<pair<vector<int>, vector<int>>> all;
    int sz = (N+1) / 2;
    vector<int> a(N);
    for(int i = 0; i < N; i++) a[i] = i + 1;
    add(a, all);
    bool stop = false;
    while(!stop){
        // cout << "All: \n";
        // for(auto p : all){
        //     cout << "P\n";
        //     for(int x : p.first) cout << x << " ";
        //     cout << "\n";
        //     for(int x : p.second) cout << x << " ";
        //     cout << "\n";
        // }
        for(int change = 0; change < sz; change++){
            for(auto& p : all){
                for(int i = 0; i < (int)p.second.size(); i++){
                    schedule(p.second[i], p.first[(i + change) % sz]);
                }
            }
            vector<int> rep = visit();
            int curr = 0;
            for(auto& p : all){
                for(int i = 0; i < (int)p.second.size(); i++){
                    if(rep[curr] == 1) swap(p.second[i], p.first[(i + change) % sz]);
                    curr++;
                }
            }
        }
        vector<pair<vector<int>, vector<int>>> nw;
        for(auto p : all){
            add(p.first, nw);
            add(p.second, nw);
        }
        all = nw;
        // cout << "All: \n";
        // for(auto p : all){
        //     cout << "P\n";
        //     for(int x : p.first) cout << x << " ";
        //     cout << "\n";
        //     for(int x : p.second) cout << x << " ";
        //     cout << "\n";
        // }
        if(sz == 1) stop = true;
        sz = (sz + 1) / 2;
    }
    vector<int> r;
    for(auto p : all){
        for(int x : p.first) r.push_back(x);
        for(int x : p.second) r.push_back(x);
    }
    answer(r);
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -