Submission #1207707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207707		jasonic	The Collection Game (BOI21_swaps)	C++20	5 / 100	10 ms	428 KiB

swaps

#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

vector<int> a;

bool compare(const int x, const int y) {
    schedule(x, y);
    vector<int> z = visit();
    assert(size(z) == 1);
    return (z[0] == 1);
}

void conquer(int l_l, int l_r, int r_l, int r_r) {
    queue<int> l, r, f;
    for(int i = l_l; i <= l_r; i++) l.push(a[i]);
    for(int i = r_l; i <= r_r; i++) r.push(a[i]);
    while(!l.empty() && !r.empty()) {
        if(compare(l.front(), r.front())) { // left is bigger
            f.push(l.front());
            l.pop();
        } else {
            f.push(r.front());
            r.pop();
        }
    }
    while(!l.empty()) {
        f.push(l.front());
        l.pop();
    }
    while(!r.empty()) {
        f.push(r.front());
        r.pop();
    }
    for(int i = l_l; i <= r_r; i++) {
        a[i] = f.front();
        f.pop();
    }
}

void divide(int l, int r) {
    if(l != r) {
        int m = (l+r)/2;
        divide(l, m);
        divide(m+1, r);
        conquer(l, m, m+1, r);
    }
}

void solve(int N, int V) {
    a = vector<int>(N);
    for(int i = 0; i < N; i++) a[i] = i+1;

    divide(0, N-1);

    answer(a);
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3-1: 0 / 3
• Subtask 3-2: 0 / 2
• Subtask 4-1: 0 / 9
• Subtask 4-2: 0 / 6
• Subtask 5-1: 0 / 9
• Subtask 5-2: 0 / 6
• Subtask 6-1: 0 / 21
• Subtask 6-2: 0 / 14
• Subtask 7-1: 0 / 9
• Subtask 7-2: 0 / 6