Submission #1188894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188894		ricardsjansons	Art Collections (BOI22_art)	C++20	20 / 100	72 ms	4468 KiB

art

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

vector<int>a;
map<vector<int>,int>mem;

void mv(int&i,int j){
    rotate(a.begin()+min(i,j),a.begin()+i+(i<j),a.begin()+max(i,j)+1);
    i=j;
}

int p(){
    if(!mem.count(a)){
        mem[a]=publish(a);
    }
    return mem[a];
}

int f(int l,int r){
    int x=r;
    while(l<r){
        int mid=(l+r)/2;
        mv(x,mid);
        int c1=p();
        mv(x,mid+1);
        int c2=p();
        if(c1<c2){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    mv(x,l);
    return x;
}

void ms(int l=0,int r=a.size()-1){
    if(l==r){
        return;
    }
    if(r-l==1){
        int c1=p();
        swap(a[l],a[r]);
        int c2=p();
        if(c1<c2){
            swap(a[l],a[r]);
        }
        return;
    }
    int mid=(l+r)/2;
    ms(l,mid);
    ms(mid+1,r);
    int c=publish(a);
    for(int i=mid+1;i<=r;i++){
        l=f(l,i)+1;
    }
}

void solve(int N) {
    a=vector<int>(N);
    iota(a.begin(),a.end(),1);
    ms();
    answer(a);
}

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