#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
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) {
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
1 ms |
544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
1 ms |
544 KB |
Output is correct |
| 8 |
Correct |
1 ms |
464 KB |
Output is correct |
| 9 |
Correct |
6 ms |
564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
592 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Correct |
5 ms |
592 KB |
Output is correct |
| 13 |
Correct |
0 ms |
464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
464 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| 16 |
Correct |
1 ms |
464 KB |
Output is correct |
| 17 |
Correct |
1 ms |
464 KB |
Output is correct |
| 18 |
Correct |
1 ms |
464 KB |
Output is correct |
| 19 |
Correct |
0 ms |
464 KB |
Output is correct |
| 20 |
Correct |
1 ms |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
1 ms |
544 KB |
Output is correct |
| 8 |
Correct |
1 ms |
464 KB |
Output is correct |
| 9 |
Correct |
6 ms |
564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
592 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Correct |
5 ms |
592 KB |
Output is correct |
| 13 |
Correct |
0 ms |
464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
464 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| 16 |
Correct |
1 ms |
464 KB |
Output is correct |
| 17 |
Correct |
1 ms |
464 KB |
Output is correct |
| 18 |
Correct |
1 ms |
464 KB |
Output is correct |
| 19 |
Correct |
0 ms |
464 KB |
Output is correct |
| 20 |
Correct |
1 ms |
464 KB |
Output is correct |
| 21 |
Correct |
1 ms |
464 KB |
Output is correct |
| 22 |
Correct |
6 ms |
608 KB |
Output is correct |
| 23 |
Correct |
6 ms |
592 KB |
Output is correct |
| 24 |
Correct |
4 ms |
548 KB |
Output is correct |
| 25 |
Correct |
7 ms |
544 KB |
Output is correct |
| 26 |
Correct |
1 ms |
464 KB |
Output is correct |
| 27 |
Correct |
9 ms |
592 KB |
Output is correct |
| 28 |
Incorrect |
125 ms |
1640 KB |
Not correct |
| 29 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
1 ms |
544 KB |
Output is correct |
| 8 |
Correct |
1 ms |
464 KB |
Output is correct |
| 9 |
Correct |
6 ms |
564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
592 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Correct |
5 ms |
592 KB |
Output is correct |
| 13 |
Correct |
0 ms |
464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
464 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| 16 |
Correct |
1 ms |
464 KB |
Output is correct |
| 17 |
Correct |
1 ms |
464 KB |
Output is correct |
| 18 |
Correct |
1 ms |
464 KB |
Output is correct |
| 19 |
Correct |
0 ms |
464 KB |
Output is correct |
| 20 |
Correct |
1 ms |
464 KB |
Output is correct |
| 21 |
Correct |
1 ms |
464 KB |
Output is correct |
| 22 |
Correct |
6 ms |
608 KB |
Output is correct |
| 23 |
Correct |
6 ms |
592 KB |
Output is correct |
| 24 |
Correct |
4 ms |
548 KB |
Output is correct |
| 25 |
Correct |
7 ms |
544 KB |
Output is correct |
| 26 |
Correct |
1 ms |
464 KB |
Output is correct |
| 27 |
Correct |
9 ms |
592 KB |
Output is correct |
| 28 |
Incorrect |
125 ms |
1640 KB |
Not correct |
| 29 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
1 ms |
544 KB |
Output is correct |
| 8 |
Correct |
1 ms |
464 KB |
Output is correct |
| 9 |
Correct |
6 ms |
564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
592 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Correct |
5 ms |
592 KB |
Output is correct |
| 13 |
Correct |
0 ms |
464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
464 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| 16 |
Correct |
1 ms |
464 KB |
Output is correct |
| 17 |
Correct |
1 ms |
464 KB |
Output is correct |
| 18 |
Correct |
1 ms |
464 KB |
Output is correct |
| 19 |
Correct |
0 ms |
464 KB |
Output is correct |
| 20 |
Correct |
1 ms |
464 KB |
Output is correct |
| 21 |
Correct |
1 ms |
464 KB |
Output is correct |
| 22 |
Correct |
6 ms |
608 KB |
Output is correct |
| 23 |
Correct |
6 ms |
592 KB |
Output is correct |
| 24 |
Correct |
4 ms |
548 KB |
Output is correct |
| 25 |
Correct |
7 ms |
544 KB |
Output is correct |
| 26 |
Correct |
1 ms |
464 KB |
Output is correct |
| 27 |
Correct |
9 ms |
592 KB |
Output is correct |
| 28 |
Incorrect |
125 ms |
1640 KB |
Not correct |
| 29 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
464 KB |
Output is correct |
| 2 |
Correct |
0 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
544 KB |
Output is correct |
| 4 |
Correct |
1 ms |
464 KB |
Output is correct |
| 5 |
Correct |
1 ms |
464 KB |
Output is correct |
| 6 |
Correct |
1 ms |
464 KB |
Output is correct |
| 7 |
Correct |
1 ms |
544 KB |
Output is correct |
| 8 |
Correct |
1 ms |
464 KB |
Output is correct |
| 9 |
Correct |
6 ms |
564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
592 KB |
Output is correct |
| 11 |
Correct |
6 ms |
592 KB |
Output is correct |
| 12 |
Correct |
5 ms |
592 KB |
Output is correct |
| 13 |
Correct |
0 ms |
464 KB |
Output is correct |
| 14 |
Correct |
0 ms |
464 KB |
Output is correct |
| 15 |
Correct |
1 ms |
464 KB |
Output is correct |
| 16 |
Correct |
1 ms |
464 KB |
Output is correct |
| 17 |
Correct |
1 ms |
464 KB |
Output is correct |
| 18 |
Correct |
1 ms |
464 KB |
Output is correct |
| 19 |
Correct |
0 ms |
464 KB |
Output is correct |
| 20 |
Correct |
1 ms |
464 KB |
Output is correct |
| 21 |
Correct |
1 ms |
464 KB |
Output is correct |
| 22 |
Correct |
6 ms |
608 KB |
Output is correct |
| 23 |
Correct |
6 ms |
592 KB |
Output is correct |
| 24 |
Correct |
4 ms |
548 KB |
Output is correct |
| 25 |
Correct |
7 ms |
544 KB |
Output is correct |
| 26 |
Correct |
1 ms |
464 KB |
Output is correct |
| 27 |
Correct |
9 ms |
592 KB |
Output is correct |
| 28 |
Incorrect |
125 ms |
1640 KB |
Not correct |
| 29 |
Halted |
0 ms |
0 KB |
- |
