Submission #1188908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188908		mareksb	Art Collections (BOI22_art)	C++17	35 / 100	91 ms	420 KiB

art

#include "art.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//
// --- Sample implementation for the task art ---
//
// To compile this program with the sample grader, place:
//     art.h art_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 art_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
int gN=0;
bool cmp(int a, int b){
    vector<int> v;
    v.push_back(a);
    v.push_back(b);
    for(int i=1;i<=gN;i++){
        if(i==a||i==b)continue;
        v.push_back(i);
    }
    int d1=publish(v);
    swap(v[0],v[1]);
    int d2=publish(v);
    return d2>d1;
}
void merg(vector<int>&a, int l, int mid, int r){
    int lsiz=mid-l+1;
    int rsiz=r-mid;
    vector<int> al(lsiz),ar(rsiz);
    for(int i=0;i<lsiz;i++){
        al[i]=a[l+i];
    }
    for(int i=0;i<rsiz;i++){
        ar[i]=a[mid+1+i];
    }
    int i=0;
    int j=0;
    int k=l;
    while(i<lsiz||j<rsiz){
        if(i<lsiz&&j<rsiz){
            if(cmp(al[i],ar[j])){
                a[k]=al[i];
                i++;
            }
            else{
                a[k]=ar[j];
                j++;
            }
        }
        else if(i<lsiz){
            a[k]=al[i];
            i++;
        }
        else{
            a[k]=ar[j];
            j++;
        }
        k++;
    }

}
void mergesrt(vector<int>& a, int l, int r){
    if(l>=r){
        return;
    }
    int mid=(l+r)/2;
    mergesrt(a,l,mid);
    mergesrt(a,mid+1,r);
    merg(a,l,mid,r);
}
void solve(int N) {
    gN=N;
    vector<int> a(N);
    for(int i=0;i<N;i++){
        a[i]=i+1;
    }
    mergesrt(a,0,N-1);
    answer(a);

}
/*
int publish(vector<int>);
void answer(vector<int>);
*/

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