Submission #406889

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
406889	2021-05-18 07:16:41	ja_kingy	Ancient Books (IOI17_books)	C++14	100 / 100	221 ms	34952 KiB

books

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
long long minimum_walk(vector<int> p, int s) {
  long long ans = 0;
  int n = p.size(), ccnt = 0;
  vector<int> mn(n), mx(n), cyc(n);
  vector<pii> evs;
  for (int i = 0; i < n; ++i) {
    ans += abs(i-p[i]);
    if (!cyc[i]) {
      ccnt++;
      cyc[i] = ccnt;
      mn[ccnt] = mx[ccnt] = i;
      for (int x = p[i]; x != i; x = p[x]) {
        cyc[x] = ccnt;
        mn[ccnt] = min(mn[ccnt], x);
        mx[ccnt] = max(mx[ccnt], x);
      }
      if (mn[ccnt] != mx[ccnt] || i == s) {
        evs.push_back({mn[ccnt], -1});
        evs.push_back({mx[ccnt], 1});
      }
    }
  }
  sort(evs.begin(), evs.end());
  int rcnt = 0, pv = -1, fst;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:54:5: warning: 'fst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     if (l == fst || r == pv) break;
      |     ^~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30