Submission #721671

#	Time	Username	Problem	Language	Result	Execution time	Memory
721671		Mr_Husanboy	Art Collections (BOI22_art)	C++17	35 / 100	163 ms	976 KiB

art

#include "art.h"
#include<bits/stdc++.h>
 
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
    return a.size();
}
 
using namespace std;

vector<int> v;
vector<vector<int>> comp;


vector<int> temp;

void sort(int l, int r){
    auto greater = [&](int i, int j)->int{
        //cout << l << ' ' << r << endl;
        if(~comp[v[i]][v[j]]) return comp[v[i]][v[j]];
        int y = publish(v);
        if(!y){
            answer(v);
        }
        swap(v[i], v[j]);
        int x = publish(v);
        if(!x){
            answer(v);
        }
        swap(v[i], v[j]);
        comp[v[i]][v[j]] = y > x; comp[v[j]][v[i]] = y < x;
        return comp[v[i]][v[j]];
    };
    if(l == r) return;
    if(l == r - 1){
        if(greater(l, r) == 1) swap(v[l], v[r]);
        return;
    }
    int m = (l + r) >> 1;
    sort(l, m);
    sort(m + 1, r);
    int cur = l;
    for(int i = l, j = m + 1; i <= m || j <= r; i ++){
        while(j <= r && (i > m || greater(i, j) == 1)){
            temp[cur] = v[j]; cur ++; j ++;
        }
        if(i <= m)
        temp[cur] = v[i];
        cur ++;
    }
    for(int i = l; i <= r; i ++) v[i] = temp[i];
    return;
}
mt19937 mt(time(NULL));

auto shuffle(int n){
    for(int i = 0; i < 3 * n; i ++){
        int a = mt() % n;
        int b = mt() % n;
        swap(v[a],v[b]);
    }
}

void solve(int n){
    v.assign(n, 0);
    temp.resize(n);
    comp.assign(n + 1, vector<int>(n + 1, -1));
    iota(all(v), 1);
    shuffle(n);
    sort(0, n - 1);
    answer(v);
}

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