Submission #867905

#	Time	Username	Problem	Language	Result	Execution time	Memory
867905		Dec0Dedd	Art Collections (BOI22_art)	C++17	100 / 100	1241 ms	1760 KiB

art

#include <bits/stdc++.h>
#include "art.h"
 
using namespace std;
 
// n <= 4 000
// q <= 4 000
 
void solve(int n) {

    vector<int> tmp, v;
    for (int i=1; i<=n; ++i) tmp.push_back(i);
    int x=publish(tmp);

    for (int i=1; i<=n; ++i) {
        vector<int> k;
        for (int j=1; j<=n; ++j) k.push_back(j);
        k.erase(k.begin()+i-1), k.insert(k.begin(), i);

        if (i > 1) v.push_back(i-1-(x-publish(k)+i-1)/2);
        else v.push_back(0);
    }

    reverse(v.begin(), v.end());
    for (int i=n-1; i>=0; --i) {
        for (int j=i+1; j<n; ++j) {
            if (v[i] <= v[j]) ++v[j];
        }
    }

    for (int i=0; i<n; ++i) ++v[i];
    reverse(v.begin(), v.end());

    vector<int> ans(n, 0);
    for (int i=0; i<n; ++i) ans[v[i]-1]=i+1;

    answer(ans);
}

Compilation message (stderr)

interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~

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