oj.uz

Submission #894593

# Submission time Handle Problem Language Result Execution time Memory
894593 2023-12-28T13:56:35 Z vjudge1 The Collection Game (BOI21_swaps) C++17
35 / 100
 35 ms 1748 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){
        int mx = 0;
        for(auto p : all){
            mx = max(mx, (int)p.second.size());
        }
        for(int change = 0; change < mx + 1; 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;
        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 464 KB Correct
3 Correct 8 ms 460 KB Correct
4 Correct 30 ms 752 KB Correct
5 Correct 31 ms 1748 KB Correct
6 Correct 30 ms 1000 KB Correct
7 Correct 31 ms 952 KB Correct
8 Correct 30 ms 752 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 460 KB Correct
3 Correct 9 ms 476 KB Correct
4 Correct 30 ms 944 KB Correct
5 Correct 30 ms 940 KB Correct
6 Correct 30 ms 1196 KB Correct
7 Correct 30 ms 1704 KB Correct
8 Correct 30 ms 948 KB Correct
9 Correct 30 ms 948 KB Correct
10 Correct 32 ms 1004 KB Correct
11 Correct 30 ms 932 KB Correct
12 Correct 30 ms 1004 KB Correct
13 Correct 30 ms 1008 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 452 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 452 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 448 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 444 KB Correct
3 Correct 9 ms 476 KB Correct
4 Correct 31 ms 1188 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 444 KB Correct
3 Correct 9 ms 476 KB Correct
4 Correct 31 ms 1188 KB Correct
5 Correct 1 ms 344 KB Correct
6 Correct 2 ms 712 KB Correct
7 Correct 9 ms 472 KB Correct
8 Correct 33 ms 1188 KB Correct
9 Correct 31 ms 756 KB Correct
10 Correct 31 ms 1196 KB Correct
11 Correct 30 ms 1264 KB Correct
12 Correct 32 ms 1264 KB Correct
13 Correct 0 ms 344 KB Correct
14 Correct 2 ms 608 KB Correct
15 Correct 9 ms 488 KB Correct
16 Correct 35 ms 1004 KB Correct

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 696 KB Correct
3 Correct 10 ms 460 KB Correct
4 Correct 30 ms 504 KB Correct
5 Runtime error 31 ms 1212 KB Execution killed with signal 13
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 2 ms 696 KB Correct
3 Correct 10 ms 460 KB Correct
4 Correct 30 ms 504 KB Correct
5 Runtime error 31 ms 1212 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.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 484 KB Correct
4 Correct 30 ms 756 KB Correct
5 Runtime error 31 ms 956 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.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 484 KB Correct
4 Correct 30 ms 756 KB Correct
5 Runtime error 31 ms 956 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 448 KB Correct
3 Correct 9 ms 468 KB Correct
4 Correct 31 ms 952 KB Correct
5 Runtime error 30 ms 936 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 448 KB Correct
3 Correct 9 ms 468 KB Correct
4 Correct 31 ms 952 KB Correct
5 Runtime error 30 ms 936 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -