# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1058717 | 2024-08-14T12:48:37 Z | shenfe1 | 고대 책들 (IOI17_books) | C++17 | 2000 ms | 105544 KB |
#include <bits/stdc++.h> #include "books.h" #pragma GCC optimize("Ofast") using namespace std; #define pb push_back #define pii pair<int,int> #define sz(s) (int)s.size() #define F first #define S second #define all(v) v.begin(),v.end() #define ll long long const int MAX=1e6+10; int n; vector<int> g[MAX]; bool use[MAX]; vector<int> vec; int pref[MAX]; struct dsu{ int f[MAX]; void init(int n){ for(int i=0;i<n;i++)f[i]=i; } int get(int v){ return (f[v]==v?v:f[v]=get(f[v])); } void unite(int a,int b){ a=get(a),b=get(b); f[a]=b; } }d; int num[MAX]; ll minimum_walk(vector<int> p,int s){ n=sz(p); int Lneed=0,Rneed=n-1; ll ans=0; for(int i=0;i<n;i++){ ans+=abs(i-p[i]); } vector<vector<int>> x; vector<pii> seg; for(int i=0;i<n;i++){ if(!use[i]){ vec.clear(); int v=i; while(!use[v]){ num[v]=sz(seg); vec.pb(v); use[v]=1; v=p[v]; } sort(all(vec)); seg.pb({vec[0],vec.back()}); x.pb(vec); } } d.init(n); for(int i=0;i<sz(seg);i++){ auto [l,r]=seg[i]; for(int j=i+1;j<sz(seg);j++){ for(int pos:x[j]){ if(l<=pos&&pos<=r){ d.unite(i,j); } } } } for(int i=0;i<n-1;i++){ if(d.get(num[i])!=d.get(num[i+1])){ ans+=2; d.unite(num[i],num[i+1]); } } for(int i=0;i<s;i++){ if(p[i]==i)ans-=2; else break; } for(int i=n-1;i>s;i--){ if(p[i]==i)ans-=2; else break; } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28252 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 3 ms | 28252 KB | Output is correct |
4 | Correct | 3 ms | 28252 KB | Output is correct |
5 | Correct | 4 ms | 28252 KB | Output is correct |
6 | Correct | 3 ms | 28252 KB | Output is correct |
7 | Correct | 3 ms | 28252 KB | Output is correct |
8 | Correct | 4 ms | 28248 KB | Output is correct |
9 | Correct | 4 ms | 28252 KB | Output is correct |
10 | Correct | 4 ms | 28252 KB | Output is correct |
11 | Correct | 3 ms | 28252 KB | Output is correct |
12 | Correct | 4 ms | 28248 KB | Output is correct |
13 | Correct | 4 ms | 28252 KB | Output is correct |
14 | Correct | 4 ms | 28252 KB | Output is correct |
15 | Correct | 4 ms | 28252 KB | Output is correct |
16 | Correct | 3 ms | 28252 KB | Output is correct |
17 | Correct | 3 ms | 28252 KB | Output is correct |
18 | Correct | 3 ms | 28252 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28252 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 3 ms | 28252 KB | Output is correct |
4 | Correct | 3 ms | 28252 KB | Output is correct |
5 | Correct | 4 ms | 28252 KB | Output is correct |
6 | Correct | 3 ms | 28252 KB | Output is correct |
7 | Correct | 3 ms | 28252 KB | Output is correct |
8 | Correct | 4 ms | 28248 KB | Output is correct |
9 | Correct | 4 ms | 28252 KB | Output is correct |
10 | Correct | 4 ms | 28252 KB | Output is correct |
11 | Correct | 3 ms | 28252 KB | Output is correct |
12 | Correct | 4 ms | 28248 KB | Output is correct |
13 | Correct | 4 ms | 28252 KB | Output is correct |
14 | Correct | 4 ms | 28252 KB | Output is correct |
15 | Correct | 4 ms | 28252 KB | Output is correct |
16 | Correct | 3 ms | 28252 KB | Output is correct |
17 | Correct | 3 ms | 28252 KB | Output is correct |
18 | Correct | 3 ms | 28252 KB | Output is correct |
19 | Correct | 4 ms | 28252 KB | Output is correct |
20 | Correct | 4 ms | 28252 KB | Output is correct |
21 | Correct | 4 ms | 28252 KB | Output is correct |
22 | Correct | 4 ms | 28248 KB | Output is correct |
23 | Correct | 4 ms | 28284 KB | Output is correct |
24 | Correct | 4 ms | 28252 KB | Output is correct |
25 | Correct | 4 ms | 28252 KB | Output is correct |
26 | Correct | 3 ms | 28108 KB | Output is correct |
27 | Correct | 4 ms | 28252 KB | Output is correct |
28 | Correct | 4 ms | 28252 KB | Output is correct |
29 | Correct | 4 ms | 28252 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28252 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 3 ms | 28252 KB | Output is correct |
4 | Correct | 3 ms | 28252 KB | Output is correct |
5 | Correct | 4 ms | 28252 KB | Output is correct |
6 | Correct | 3 ms | 28252 KB | Output is correct |
7 | Correct | 3 ms | 28252 KB | Output is correct |
8 | Correct | 4 ms | 28248 KB | Output is correct |
9 | Correct | 4 ms | 28252 KB | Output is correct |
10 | Correct | 4 ms | 28252 KB | Output is correct |
11 | Correct | 3 ms | 28252 KB | Output is correct |
12 | Correct | 4 ms | 28248 KB | Output is correct |
13 | Correct | 4 ms | 28252 KB | Output is correct |
14 | Correct | 4 ms | 28252 KB | Output is correct |
15 | Correct | 4 ms | 28252 KB | Output is correct |
16 | Correct | 3 ms | 28252 KB | Output is correct |
17 | Correct | 3 ms | 28252 KB | Output is correct |
18 | Correct | 3 ms | 28252 KB | Output is correct |
19 | Correct | 4 ms | 28252 KB | Output is correct |
20 | Correct | 4 ms | 28252 KB | Output is correct |
21 | Correct | 4 ms | 28252 KB | Output is correct |
22 | Correct | 4 ms | 28248 KB | Output is correct |
23 | Correct | 4 ms | 28284 KB | Output is correct |
24 | Correct | 4 ms | 28252 KB | Output is correct |
25 | Correct | 4 ms | 28252 KB | Output is correct |
26 | Correct | 3 ms | 28108 KB | Output is correct |
27 | Correct | 4 ms | 28252 KB | Output is correct |
28 | Correct | 4 ms | 28252 KB | Output is correct |
29 | Correct | 4 ms | 28252 KB | Output is correct |
30 | Correct | 143 ms | 49160 KB | Output is correct |
31 | Correct | 134 ms | 47808 KB | Output is correct |
32 | Execution timed out | 2041 ms | 105544 KB | Time limit exceeded |
33 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 28252 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28252 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 3 ms | 28252 KB | Output is correct |
4 | Correct | 3 ms | 28252 KB | Output is correct |
5 | Correct | 4 ms | 28252 KB | Output is correct |
6 | Correct | 3 ms | 28252 KB | Output is correct |
7 | Correct | 3 ms | 28252 KB | Output is correct |
8 | Correct | 4 ms | 28248 KB | Output is correct |
9 | Correct | 4 ms | 28252 KB | Output is correct |
10 | Correct | 4 ms | 28252 KB | Output is correct |
11 | Correct | 3 ms | 28252 KB | Output is correct |
12 | Correct | 4 ms | 28248 KB | Output is correct |
13 | Correct | 4 ms | 28252 KB | Output is correct |
14 | Correct | 4 ms | 28252 KB | Output is correct |
15 | Correct | 4 ms | 28252 KB | Output is correct |
16 | Correct | 3 ms | 28252 KB | Output is correct |
17 | Correct | 3 ms | 28252 KB | Output is correct |
18 | Correct | 3 ms | 28252 KB | Output is correct |
19 | Correct | 4 ms | 28252 KB | Output is correct |
20 | Correct | 4 ms | 28252 KB | Output is correct |
21 | Correct | 4 ms | 28252 KB | Output is correct |
22 | Correct | 4 ms | 28248 KB | Output is correct |
23 | Correct | 4 ms | 28284 KB | Output is correct |
24 | Correct | 4 ms | 28252 KB | Output is correct |
25 | Correct | 4 ms | 28252 KB | Output is correct |
26 | Correct | 3 ms | 28108 KB | Output is correct |
27 | Correct | 4 ms | 28252 KB | Output is correct |
28 | Correct | 4 ms | 28252 KB | Output is correct |
29 | Correct | 4 ms | 28252 KB | Output is correct |
30 | Correct | 143 ms | 49160 KB | Output is correct |
31 | Correct | 134 ms | 47808 KB | Output is correct |
32 | Execution timed out | 2041 ms | 105544 KB | Time limit exceeded |
33 | Halted | 0 ms | 0 KB | - |