Submission #598058

#	Time	Username	Problem	Language	Result	Execution time	Memory
598058		jhnah917	Art Collections (BOI22_art)	C++17	35 / 100	191 ms	256 KiB

art

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

int n, now, lst;
vector<int> v;

bool compare(int a, int b){
    if(a == b) return false;
    int pa = find(v.begin(), v.end(), a) - v.begin();
    int pb = find(v.begin(), v.end(), b) - v.begin();
    swap(v[pa], v[pb]);
    lst = publish(v);
    swap(v[pa], v[pb]);
    if(pa < pb) return now < lst;
    return now > lst;
}

int p(int x){ return (x - 1) / 2; }
int l(int x){ return x * 2 + 1; }
int r(int x){ return x * 2 + 2; }

void heapify(int t, int sz){
    while(l(t) < sz){
        if(r(t) < sz && compare(v[l(t)], v[r(t)]) && compare(v[t], v[r(t)])){
            swap(v[t], v[r(t)]); now = lst; t = r(t);
        }
        else if(compare(v[t], v[l(t)])){
            swap(v[t], v[l(t)]); now = lst; t = l(t);
        }
        else break;
    }
}

void make_heap(){
    for(int i=n-1; i; i--){
        if(compare(v[i], v[p(i)])) continue;
        swap(v[i], v[p(i)]); now = lst;
        heapify(i, n);
    }
}

void heap_sort(){
    make_heap();
    int sz = n;
    while(sz > 1){
        swap(v[0], v[--sz]); now = publish(v);
        if(sz > 1) heapify(0, sz);
    }
}

void solve(int _n){
    n = _n; v.resize(n);
    iota(v.begin(), v.end(), 1);
    now = publish(v);
    heap_sort();
    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