Submission #1246390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246390		adam17	Art Collections (BOI22_art)	C++20	50 / 100	383 ms	452 KiB

art

#include "art.h"
// #include <algorithm>
#include <iostream>
using namespace std;

int NN;
vector<int> X;
int def;
// int odsazeni;

bool compare(int a, int b) {
    vector<int> V(NN);
    for (int i = 0; i < NN; i++) {
        V[i] = i + 1;
    }
    V[a - 1] = b;
    V[b - 1] = a;
    int x = publish(V);
    return x > def;
}

void sort(int i, int j) {
    // for (int i = 0; i < odsazeni; i++) cout << "  "; cout << "Running sort(" << i << ", " << j << ") {\n";
    // odsazeni++;
    // int pocet = 0;
    if (j - i > 1) {
        int s = (i + j) / 2;
        sort(i, s);
        sort(s, j);
        vector<int> Y(0);
        int a = i, b = s;
        while ((a < s) && (b < j)) {
            // pocet++;
            if (compare(X[a], X[b])) {
                Y.push_back(X[a]);
                a++;
            } else {
                Y.push_back(X[b]);
                b++;
            }
        }
        while (a < s) {
            Y.push_back(X[a]);
            a++;
        }
        while (b < s) {
            Y.push_back(X[b]);
            b++;
        }
        for (int ii = 0; ii < Y.size(); ii++) {
            X[i + ii] = Y[ii];
        }
    }
    // odsazeni--;
    // for (int i = 0; i < odsazeni; i++) cout << "  "; cout << "} (" << pocet << " na " << j - i << ")\n";
}

void solve(int N) {
    // odsazeni = 0;
    NN = N;
    X.resize(N);
    for (int i = 0; i < N; i++) {
        X[i] = i + 1;
    }
    def = publish(X);
    sort(0, N);
    answer(X);
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30