oj.uz

Submission #894550

# Submission time Handle Problem Language Result Execution time Memory
894550 2023-12-28T12:33:57 Z vjudge1 The Collection Game (BOI21_swaps) C++17
35 / 100
 38 ms 1468 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) % (int)p.first.size()]);
                }
            }
            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) % (int)p.first.size()]);
                    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 444 KB Correct
3 Correct 9 ms 444 KB Correct
4 Correct 33 ms 676 KB Correct
5 Correct 33 ms 696 KB Correct
6 Correct 31 ms 1468 KB Correct
7 Correct 34 ms 928 KB Correct
8 Correct 31 ms 1204 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 444 KB Correct
3 Correct 9 ms 456 KB Correct
4 Correct 32 ms 1228 KB Correct
5 Correct 33 ms 1196 KB Correct
6 Correct 31 ms 1180 KB Correct
7 Correct 32 ms 1432 KB Correct
8 Correct 38 ms 1184 KB Correct
9 Correct 31 ms 948 KB Correct
10 Correct 30 ms 956 KB Correct
11 Correct 33 ms 692 KB Correct
12 Correct 31 ms 696 KB Correct
13 Correct 31 ms 712 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 448 KB Correct

Subtask #3-2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 448 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 2 ms 608 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 448 KB Correct
3 Correct 9 ms 460 KB Correct
4 Correct 32 ms 932 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 448 KB Correct
3 Correct 9 ms 460 KB Correct
4 Correct 32 ms 932 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 2 ms 704 KB Correct
7 Correct 9 ms 448 KB Correct
8 Correct 35 ms 936 KB Correct
9 Correct 31 ms 1228 KB Correct
10 Correct 31 ms 976 KB Correct
11 Correct 32 ms 1204 KB Correct
12 Correct 31 ms 972 KB Correct
13 Correct 0 ms 344 KB Correct
14 Correct 2 ms 448 KB Correct
15 Correct 9 ms 704 KB Correct
16 Correct 32 ms 948 KB Correct

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 3 ms 444 KB Correct
3 Correct 9 ms 712 KB Correct
4 Correct 33 ms 952 KB Correct
5 Runtime error 32 ms 948 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 3 ms 444 KB Correct
3 Correct 9 ms 712 KB Correct
4 Correct 33 ms 952 KB Correct
5 Runtime error 32 ms 948 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 444 KB Correct
3 Correct 9 ms 456 KB Correct
4 Correct 33 ms 1444 KB Correct
5 Runtime error 31 ms 696 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 444 KB Correct
3 Correct 9 ms 456 KB Correct
4 Correct 33 ms 1444 KB Correct
5 Runtime error 31 ms 696 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Correct
2 Correct 2 ms 608 KB Correct
3 Correct 9 ms 432 KB Correct
4 Correct 34 ms 932 KB Correct
5 Runtime error 36 ms 1008 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Correct
2 Correct 2 ms 608 KB Correct
3 Correct 9 ms 432 KB Correct
4 Correct 34 ms 932 KB Correct
5 Runtime error 36 ms 1008 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -