Submission #588204

#	Time	Username	Problem	Language	Result	Execution time	Memory
588204		1zaid1	Art Collections (BOI22_art)	C++17	20 / 100	125 ms	1640 KiB

art

#include "art.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1e4+4;
map<pair<int, int>, int> vis, mp;
int sum, cnt, in[M], out[M];
vector<int> v, node[M], top;
bitset<10004> vi;
int done(int i, int j) {
    int a = v[i], b = v[j];
    if (!vis[{a, b}]) {
        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);
    sum = publish(v);
    
    while (sum) {
        for (int i = 0; i < n-1; i++) {
            if (done(i, i+1)) {
                out[v[i]]++;
                in[v[i+1]]++;
                node[v[i]].push_back(v[i+1]);
            } else {
                node[v[i+1]].push_back(v[i]);
                out[v[i+1]]++;
                in[v[i]]++;
            }
        }

        for (int i = 1; i <= n; i++) if (!vi[i]) dfs(i); vi = 0;
        reverse(top.begin(), top.end());
        vector<int> a, b, c;
        for (int i:top) {
            if (!in[i]) a.push_back(i);
            else if (out[i]) b.push_back(i);
            else c.push_back(i);
        }

        // cout << "Src: "; for (int i:a) cout << i << ' '; cout << endl;
        // cout << "Mid: "; for (int i:b) cout << i << ' '; cout << endl;
        // cout << "Snk: "; for (int i:c) cout << i << ' '; cout << endl;

        for (int i:b) a.push_back(i);
        for (int i:c) a.push_back(i);
        // cout << "Fin: "; for (int &i:a) cout << i << ' '; cout << endl;
        v = a;
        top.clear();
        sum = publish(v);
    } answer(v);
}

Compilation message (stderr)

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