답안 #585824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585824	2022-06-29T11:46:32 Z	InternetPerson10	고대 책들 (IOI17_books)	C++17	22 / 100	2000 ms	190024 KB

books

#include "books.h"
#include <bits/stdc++.h>
typedef long long ll;
 
using namespace std;
 
vector<vector<int>> adj;
vector<int> dist;
 
long long minimum_walk(vector<int> p, int s) {
    ll tot = 0;
    int n = p.size();
    vector<bool> taken(n, false);
    int g = n;
    adj.resize(n);
    for(int i = 1; i < n; i++) {
        adj[i].push_back(i-1);
        adj[i-1].push_back(i);
    }
    for(int i = 0; i < n; i++) {
        if(!taken[i]) {
            adj.push_back(vector<int>());
            int x = i;
            int l = i, r = i;
            while(!taken[x]) {
                taken[x] = true;
                tot += abs(x - p[x]);
                x = p[x];
                l = min(l, x);
                r = max(r, x);
                adj[x].push_back(g);
            }
            for(int j = l; j <= r; j++) {
                adj[g].push_back(j);
            }
            g++;
        }
    }
    taken.clear();
    taken.resize(g, false);
    dist.resize(g, 1e9 + 7);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s + 1});
    while(pq.size()) {
        auto pa = pq.top();
        pq.pop();
        int len = pa.first, x = abs(pa.second) - 1;
        if(taken[x]) continue;
        taken[x] = true;
        if(x < n) {
            if(pa.second > 0) {
                tot += 2;
            }
        }
        for(int ch : adj[x]) {
            int goLength;
            if(max(ch, x) < n) {
                goLength = len + 1;
            }
            else {
                goLength = len;
            }
            if(dist[ch] < goLength) continue;
            if(dist[ch] == goLength && len != goLength) continue;
            dist[ch] = goLength;
            if(goLength == len + 1) pq.push({goLength, ch+1});
            else pq.push({goLength, -ch-1});
        }
    }
    for(int i = 0; i < n; i++) {
        if(p[i] == i && i != s) tot -= 2;
        else break;
    }
    for(int i = n-1; i >= 0; i--) {
        if(p[i] == i && i != s) tot -= 2;
        else break;
    }
    return max(tot - 2, 0LL);
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	2 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct

Subtask #3

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	2 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Execution timed out	2097 ms	190024 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	340 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3862'
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	2 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Execution timed out	2097 ms	190024 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-