Submission #1188954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188954		herissonwoww	Art Collections (BOI22_art)	C++20	100 / 100	770 ms	472 KiB

art

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

//void MergeSort(vector<int> v, int left, int right){
//    if(left>=right)
//        return;
//    int mid = left+(right-left)/2;
//    MergeSort(v, left, mid);
//    MergeSort(v, mid+1, right);
//    merge_part(v, left, mid, right);
//}
//void merge_part(vector<int>v, int left, int mid, int right){
//    int n1 = mid-left+1;
//    int n2 = right-mid;
//
//}

void solve(int n) {
    vector <int> vals(n);
    for(int i = 0; i < n; i++){
        vals[i] = i+1;
    }
    int k1 = publish(vals);
    for(int i = 1; i < n; i++){
        vector <int> valstemp = vals;
        for(int j = i-1; j >= 0 ; j--){
           swap(valstemp[j], valstemp[j + 1]);
        }
        int k2 = publish(valstemp);
        int b = (k2-k1+i)/2;
        int a = i-b;
        int newpos = b;
        for(int j = 1;j <= b;j++)
            swap(valstemp[j - 1], valstemp[j]);
        swap(vals, valstemp);
        k1 = k1-a;
    }
    answer(vals);
//    if(1==1){
//        int k = publish(vals);
//        cout << k << endl;
//        vals = {2,1,3,4,5};
//        k = publish(vals);
//        cout << k << endl;
//        vals = {2,3,1,4,5};
//        k = publish(vals);
//        cout << k << endl;
//        vals = {2,3,4,1,5};
//        k = publish(vals);
//        cout << k << endl;
//        vals = {2,3,4,5,1};
//        k = publish(vals);
//        cout << k << endl;
//        return;
//    }
//    if(n <= 6){
//        do {
//            int k = publish(vals);
//            if(k==0){
//                answer(vals);
//                return;
//            }
//        } while (next_permutation(vals.begin(), vals.end()));
//
//        assert(0);
//    }
//    if(n<=40){
//        for(int i = 0; i < n-1; i++){
//            for(int j = 0; j < n-1; j++){
//                int kfirst = publish(vals);
//                swap(vals[j],vals[j+1]);
//                int ksecond = publish(vals);
//                if(kfirst < ksecond){
//                    swap(vals[j],vals[j+1]);
//                }
//            }
//        }
//        answer(vals);
//        return;
//    }

//    int p = 0;
//    int k1 = publish(vals);
//
//    valstemp[n-1] = vals[0];
//    for(int i = 0; i < n-1; i++){
//        valstemp[i] = vals[i+1];
//    }
//    int k2 = publish(valstemp);
//    int b = (k2-k1+p-1)/2;
//    int a = p-1-b;
//    int newpos = b+1;
//
//    for(int i = newpos+1; i < newpos+a; i++){
//        valstemp[i] = valstemp[i-1];
//    }
//    valstemp[newpos] = vals[p];
//    publish(valstemp);
//    cout << k1 << ' ' << k2 << ' ' << p << endl;


}

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