Submission #675992

#	Time	Username	Problem	Language	Result	Execution time	Memory
675992		Tigerpants	Art Collections (BOI22_art)	C++17	100 / 100	1449 ms	728 KiB

art

#include "art.h"

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <queue>
#include <iomanip>
#include <cmath>
#include <string>

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<vll> vvll;
typedef vector<vld> vvld;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef set<ll> sll;
typedef set<pll> spll;
typedef map<pll, ll> mpll_ll;
typedef map<ll, pll> mll_pll;
const ll bitset_size = 256;
typedef bitset<bitset_size> bits;
typedef vector<bits> vbits;
typedef string str;
typedef vector<str> vstr;

#define rep(x, a, b) for (ll x = a; x < b; x++)
#define rev_rep(x, a, b) for (ll x = a; x >= b; x--)
#define itr_rep(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, b) a.resize(b)
#define sort_all(a) sort(all(a))
#define pb(a) push_back(a)
#define fill_sz(a, b) fill_n(a.begin, sz(a), b)

vector<int> rotate(vector<int> a) {
    int b = a[0];
    rep(i, 1, sz(a)) {
        a[i - 1] = a[i];
    }
    a[sz(a) - 1] = b;
    return a;
}

void solve(int N) {
    vll complaints(N, 0); // complaints[i] contains the number of complaints of {i, i + 1, i + 2, .., N - 1, 0, 1, .., i - 1}
    vector<int> order(N);
    rep(i, 0, N) {order[i] = i + 1;}
    rep(i, 0, N) {
        complaints[i] = publish(order);
        order = rotate(order);
    }
    vpll fame(N);
    rep(i, 0, N) {
        fame[i] = mp(complaints[i] - complaints[(i + 1) % N], i);
    }
    sort_all(fame);
    rep(i, 0, N) {
        order[i] = fame[i].second + 1;
    }
    answer(order);
}

Compilation message (stderr)

art.cpp: In function 'std::vector<int> rotate(std::vector<int>)':
art.cpp:39:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 | #define rep(x, a, b) for (ll x = a; x < b; x++)
      |                                       ^
art.cpp:52:5: note: in expansion of macro 'rep'
   52 |     rep(i, 1, sz(a)) {
      |     ^~~
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