답안 #588204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588204	2022-07-02T19:01:08 Z	1zaid1	Art Collections (BOI22_art)	C++17	20 / 100	125 ms	1640 KB

#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) {
      |        ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	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

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	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

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	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	-

Subtask #4
0 / 15.0

#	결과	실행 시간	메모리	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	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	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	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	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	-

답안 #588204

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 15.0

Subtask #4 0 / 15.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 15.0

Subtask #4
0 / 15.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0