Submission #1186316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186316		qwusha	Art Collections (BOI22_art)	C++20	100 / 100	742 ms	476 KiB

art

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;

#include "art.h"


vector<int> move(vector<int> a, int ind) {
    int c = a[ind];
    for (int i = ind; i < a.size() - 1; i++) {
        a[i] = a[i + 1];
    }
    a[a.size() - 1] = c;
    return a;
}

void solve(int n) {
    vector<int> pos(n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    int k = publish(a);
    int m = publish(move(a, 0));
    pos[0] = (k - m + n - 1) / 2;
    for (int i = 1; i < n - 1; i++) {
        m = publish(move(a, i));
        pos[i] = (k - m + n - (i + 1)) / 2;
    }
    vector<int> res(n, -1);
    for (int i = 0; i < n - 1; i++) {
        int cur = 0;
        for (int j = 0; j < n; j++) {
            if (res[j] == -1) {
                if (cur == pos[i]) {
                    res[j] = i + 1;
                    break;
                }
                cur++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (res[i] == -1)
            res[i] = n;
    }
    answer(res);
}

Compilation message (stderr)

art.cpp:8:11: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
    8 | int inf = 1e15;
      |           ^~~~

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