Submission #587874

#	Time	Username	Problem	Language	Result	Execution time	Memory
587874		1zaid1	Art Collections (BOI22_art)	C++17	0 / 100	1 ms	464 KiB

art

#include "art.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> vis, mp;
vector<int> v, node[10000], top;
bitset<10000> vi;
int sum = 0, cnt;
int done(int i, int j) {
    int a = v[i], b = v[j];
    if (!vis[{a, b}]) {
        // cout << cnt++ << endl;
        vis[{a, b}] = 1;
        vis[{b, a}] = 1;
        swap(v[i], v[j]);
        int now = publish(v);
        swap(v[i], v[j]);
        mp[{a, b}] = (sum-now) < 0;
        mp[{b, a}] = !mp[{a, b}];
    } return mp[{a, b}];
}

void dfs(int s) {
    vi[s] = true;
    for (int i:node[s]) if (!vi[i]) dfs(i);
    top.push_back(s);
}

void solve(int n) {
    for (int i = 1; i <= n; i++) v.push_back(i);
    int t = n;
    while (t--) {
        sum = publish(v);
        for (int i = 0; i < n; i++) {
            if (done(v[i], v[i+1])) node[v[i]].push_back(v[i+1]);
            else node[v[i+1]].push_back(v[i]);
        }

        for (int i = 1; i <= n; i++) if (!vi[i]) dfs(i); vi = 0;
        reverse(top.begin(), top.end());
        v = top;
        top.clear();
    } answer(v);
}

Compilation message (stderr)

art.cpp: In function 'void solve(int)':
art.cpp:38:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   38 |         for (int i = 1; i <= n; i++) if (!vi[i]) dfs(i); vi = 0;
      |         ^~~
art.cpp:38:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   38 |         for (int i = 1; i <= n; i++) if (!vi[i]) dfs(i); vi = 0;
      |                                                          ^~
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