Submission #573045

#	Time	Username	Problem	Language	Result	Execution time	Memory
573045		MohamedFaresNebili	Art Collections (BOI22_art)	C++17	100 / 100	1597 ms	764 KiB

art

#include <bits/stdc++.h>
#include "art.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin(), (x).end()

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

/**

        void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...) {
            va_list args;
            va_start(args, msg);
            vfprintf(stdout, msg, args);
            fprintf(stdout, "\n");
            va_end(args);
            exit(0);
        }

        namespace {
            int N;
            int Q = 0;
            const int MAX_Q = 4000;
            const int MAX_N = 4000;
            vector<int> solution;
        }  // namespace


        int publish(vector<int> R) {
            printf("publish({");
            for(int i = 0; i < int(R.size()); ++i) {
                if(i == 0)
                    printf("%d", R[i]);
                else
                    printf(", %d", R[i]);
            }
            printf("})\n");
            fflush(stdout);

            if (++Q > MAX_Q)
                result("Too many published rankings!");

            if (int(R.size()) != N)
                result("Invalid published ranking!");

            set<int> chosen;
            for(auto &x : R) {
                if(x < 1 || x > N || chosen.count(x))
                    result("Invalid published ranking!");
                chosen.insert(x);
            }
            vector<int> positions(N+1);
            for(int i = 0; i < N; ++i)
                positions[R[i]] = i;

            int complaints = 0;
            for(int i = 0; i < N; ++i) {
                for(int j = i+1; j < N; ++j) {
                    if(positions[solution[i]] > positions[solution[j]])
                        ++complaints;
                }
            }

            return complaints;
        }

        void __attribute__((noreturn)) answer(vector<int> R) {
            printf("answer({");
            for(int i = 0; i < int(R.size()); ++i) {
                if(i == 0)
                    printf("%d", R[i]);
                else
                    printf(", %d", R[i]);
            }
            printf("})\n");
            fflush(stdout);


            if(R == solution)
                result("Correct: %d published ranking(s).", Q);
            else
                result("Wrong answer!");
        }
**/
        void solve(int N) {
            vector<int> res(N), arr(N); vector<int> R;
            for(int l = 1; l <= N; l++) R.pb(l);
            for(int l = 0; l < N; l++) {
                arr[l] = publish(R);
                for(int i = 1; i < N; i++)
                    swap(R[i], R[i - 1]);
            }
            for(int l = 0; l < N; l++)
                res[(arr[l] - arr[(l + 1) % N] + N) / 2] = l + 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