Submission #980091

#	Time	Username	Problem	Language	Result	Execution time	Memory
980091		asdfgrace	Art Collections (BOI22_art)	C++17	0 / 100	0 ms	344 KiB

art

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

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
number of pairs (x, y)
so that g.at[x] < g.at[y] and r.at[x] > r.at[y]
what about pairs (x, y)
so that g.at[x] > g.at[y] and r.at[y] < r.at[x]
basically
number of "inversions" when you replace each value i in r with g.at[i]
when there are 0 inversions you just submit whatever you guessed g was
useful guesses?
identity permutation first obvs
g.at[i] = i for all i
gives number of inversions in r
can probably then find contribution of each index?
if we swap any two elements, does it reduce the number of inversions?
if yes, swap them; else don't
this should make n^2 guesses ez it's like bubble sort
can some other sort be applied here?
maybe some kind of sort calculating contribution of each elem?
like take the first element and make it last
so you find the rank of the first elem?
so you find how much the number of inversions changes by
and basically
the increase in the number of inversions
is probably useful
and can be used to determine the position of the element
dif = (elems after v[0]) - (elems before v[0])
-dif = (elems before v[0]) - (elems after v[0])
*/

void solve(int n) {
  vector<int> v(n), at(n);
  iota(v.begin(), v.end(), 1);
  int inv1 = publish(v), inv2;
  for (int i = 0; i < n - 1; i++) {
    vector<int> v2;
    for (int i = 1; i < n; i++) v2.push_back(v[i]);
    v2.push_back(v[0]);
    inv2 = publish(v2);
    int dif = inv1 - inv2, ind = (n - 1 + dif) / 2;
    at[v[0] - 1] = ind;
    swap(v, v2);
    swap(inv1, inv2);
  }
  vector<int> res(n);
  for (int i = 0; i < n; i++) {
    res[at[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: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30