Submission #721609

#	Time	Username	Problem	Language	Result	Execution time	Memory
721609		MDSPro	Art Collections (BOI22_art)	C++17	35 / 100	178 ms	336 KiB

art

#include "art.h"
//
// --- 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
//
#include <iostream>
#include <algorithm>
#include <numeric>
#include <random>
#include <ctime>

using namespace std;

int pub(vector<int> p){
    p.erase(p.begin());
    return publish(p);
}

void solve(int N) {
    mt19937 rnd(time(0));
    uniform_int_distribution <int>get_rand(1, N);

    vector<int> p(N+1); iota(p.begin(),p.end(),0);
    vector<tuple<int,int,int>> segs;
    segs.push_back({(int)get_rand(rnd),1,N}); 
    while(segs.size() > 0){
        int x = pub(p);
        // if(x == 0) break;
        vector<tuple<int,int,int>> nsegs;
        vector<int> np(N+1);

        for(auto seg: segs){
            int mid = get<0>(seg);
            int l = get<1>(seg);
            int r = get<2>(seg);

            int pl = l,pr = r;
            for(int i = l; i <= r; ++i){
                if(i == mid) continue;
                swap(p[i],p[mid]);
                int y = pub(p);
                swap(p[i],p[mid]);
                
                if((i < mid) && (y < x) || (i > mid) && (y > x)) {
                    np[pr--] = p[i];
                } else {
                    np[pl++] = p[i];
                }

            }
            np[pl] = p[mid];
            if(r-pr > 1) {
                uniform_int_distribution<int> get_rand(pr+1, r);
                nsegs.push_back({(int)get_rand(rnd),pr+1,r});
            }

            if(pl-l > 1){
                uniform_int_distribution <int> get_rand(l, pl-1);
                nsegs.push_back({(int)get_rand(rnd),l,pl-1});
            }
        }

        for(int i = 1; i <= N; ++i) if(np[i] == 0) np[i] = p[i];

        p = np;
        segs = nsegs;
    }

    p.erase(p.begin());
    answer(p);
}

Compilation message (stderr)

art.cpp: In function 'void solve(int)':
art.cpp:52:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |                 if((i < mid) && (y < x) || (i > mid) && (y > x)) {
      |                    ~~~~~~~~~~^~~~~~~~~~
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