Submission #1115107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115107		_callmelucian	Art Collections (BOI22_art)	C++17	50 / 100	661 ms	1544 KiB

art

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int curInversion;

void mixSorted (vector<int> &vec, int l, int r, int sep) {
    // mix sorted segment [l; sep) and [sep; r]
    while (sep - l > 0 && r - sep + 1 > 0) {
        swap(vec[l], vec[sep]);
        int inversions = publish(vec);

        if (curInversion > inversions) {
            int u = vec[sep]; vec.erase(vec.begin() + sep);
            vec.insert(vec.begin() + l + 1, u);
            l++, sep++, curInversion -= sep - l;
        }
        else swap(vec[l], vec[sep]), l++;
    }
}

void mergeSort (vector<int> &vec, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    mergeSort(vec, l, mid), mergeSort(vec, mid + 1, r);
    mixSorted(vec, l, r, mid + 1);
}

void solve (int n) {
    vector<int> vec(n);
    for (int i = 1; i <= n; i++) vec[i - 1] = i;
    curInversion = publish(vec);

    mergeSort(vec, 0, n - 1);
    answer(vec);
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve(7);

    return 0;
}
#endif // LOCAL

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: 0 / 20
• Subtask 6: 0 / 30