oj.uz

Submission #894551

# Submission time Handle Problem Language Result Execution time Memory
894551 2023-12-28T12:36:37 Z vjudge1 The Collection Game (BOI21_swaps) C++17
35 / 100
 35 ms 1732 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;
    int Times = 0;
    while(!stop){
        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()]);
                }
            }
            if(Times == V){
                break;
            }
            vector<int> rep = visit();
            Times++;
            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 440 KB Correct
3 Correct 10 ms 448 KB Correct
4 Correct 34 ms 720 KB Correct
5 Correct 31 ms 940 KB Correct
6 Correct 32 ms 1732 KB Correct
7 Correct 32 ms 952 KB Correct
8 Correct 33 ms 1192 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Correct
2 Correct 2 ms 444 KB Correct
3 Correct 9 ms 452 KB Correct
4 Correct 31 ms 676 KB Correct
5 Correct 31 ms 1184 KB Correct
6 Correct 32 ms 1192 KB Correct
7 Correct 35 ms 1192 KB Correct
8 Correct 31 ms 696 KB Correct
9 Correct 32 ms 1184 KB Correct
10 Correct 32 ms 1204 KB Correct
11 Correct 31 ms 968 KB Correct
12 Correct 31 ms 956 KB Correct
13 Correct 31 ms 952 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 0 ms 344 KB Correct
4 Correct 2 ms 444 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 700 KB Correct
3 Correct 11 ms 436 KB Correct
4 Correct 31 ms 1436 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 700 KB Correct
3 Correct 11 ms 436 KB Correct
4 Correct 31 ms 1436 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 2 ms 444 KB Correct
7 Correct 9 ms 440 KB Correct
8 Correct 32 ms 1432 KB Correct
9 Correct 34 ms 1184 KB Correct
10 Correct 33 ms 1192 KB Correct
11 Correct 32 ms 1692 KB Correct
12 Correct 31 ms 1224 KB Correct
13 Correct 0 ms 344 KB Correct
14 Correct 2 ms 444 KB Correct
15 Correct 9 ms 460 KB Correct
16 Correct 32 ms 964 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 452 KB Correct
3 Correct 10 ms 460 KB Correct
4 Correct 34 ms 1184 KB Correct
5 Incorrect 31 ms 952 KB Not correct
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 452 KB Correct
3 Correct 10 ms 460 KB Correct
4 Correct 34 ms 1184 KB Correct
5 Incorrect 31 ms 952 KB Not correct
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 3 ms 440 KB Correct
3 Correct 9 ms 456 KB Correct
4 Correct 33 ms 1684 KB Correct
5 Incorrect 33 ms 952 KB Not correct
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 3 ms 440 KB Correct
3 Correct 9 ms 456 KB Correct
4 Correct 33 ms 1684 KB Correct
5 Incorrect 33 ms 952 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 452 KB Correct
3 Correct 9 ms 708 KB Correct
4 Correct 32 ms 992 KB Correct
5 Incorrect 35 ms 1696 KB Not correct
6 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 452 KB Correct
3 Correct 9 ms 708 KB Correct
4 Correct 32 ms 992 KB Correct
5 Incorrect 35 ms 1696 KB Not correct
6 Halted 0 ms 0 KB -