Submission #574572

#	Time	Username	Problem	Language	Result	Execution time	Memory
574572		cheissmart	Art Collections (BOI22_art)	C++17	100 / 100	1508 ms	664 KiB

art

#include "art.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) (v).size()
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

void solve(int n) {
    vi aux;
    for(int i = 0; i < n; i++) {
        vi p(n); iota(ALL(p), 1);
        p.erase(p.begin() + i);
        p.insert(p.begin(), i + 1);
        aux.PB(publish(p));
    }
    int tt = aux[0];
    for(int i = 0; i < n; i++) {
        assert((aux[i] - tt + i) % 2 == 0);
        aux[i] = (aux[i] - tt + i) / 2;
    }
    vi s(n); iota(ALL(s), 0);
    vi ans;
    for(int i = n - 1; i >= 0; i--) {
        ans.PB(s[aux[i]]);
        s.erase(s.begin() + aux[i]);
    }
    reverse(ALL(ans));

    vi res(n);
    for(int i = 0; i < n; i++)
        res[ans[i]] = i + 1;
    answer(res);

}

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