Submission #578565

#	Time	Username	Problem	Language	Result	Execution time	Memory
578565		Jarif_Rahman	Art Collections (BOI22_art)	C++17	100 / 100	1653 ms	760 KiB

art

#include "art.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

void solve(int n){
    vector<int> s(n);
    vector<int> pos(n, -1);
    vector<bool> found(n, 0);
    for(int i = 0; i < n; i++) s[i] = i+1;

    int ls = publish(s);

    for(int i = 0; i < n-1; i++){
        int x = s[0];
        s.erase(s.begin());
        s.insert(s.begin()+n-1-i, x);
        int c = publish(s);
        int a = n-i-1;
        int b = c-ls;

        ls = c;

        int k = (a-b)/2;
        for(int j = 1; j <= n; j++){
            if(found[j-1]) continue;
            if(k == 0){
                pos[x-1] = j;
                found[j-1] = 1;
                break;
            }
            k--;
        }
    }

    for(int i = 0; i < n; i++){
        if(pos[i] == -1){
            for(int j = 0; j < n; j++) if(!found[j]) pos[i] = j+1, found[j] = 1;
        }
    }

    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[pos[i]-1] = i+1;

    answer(ans);
}

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