# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1058720 | 2024-08-14T12:49:52 Z | shenfe1 | Ancient Books (IOI17_books) | C++17 | 6 ms | 28252 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28248 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 4 ms | 28252 KB | Output is correct |
4 | Correct | 4 ms | 28252 KB | Output is correct |
5 | Incorrect | 4 ms | 28248 KB | 3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28248 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 4 ms | 28252 KB | Output is correct |
4 | Correct | 4 ms | 28252 KB | Output is correct |
5 | Incorrect | 4 ms | 28248 KB | 3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28248 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 4 ms | 28252 KB | Output is correct |
4 | Correct | 4 ms | 28252 KB | Output is correct |
5 | Incorrect | 4 ms | 28248 KB | 3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 28248 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 28248 KB | Output is correct |
2 | Correct | 4 ms | 28252 KB | Output is correct |
3 | Correct | 4 ms | 28252 KB | Output is correct |
4 | Correct | 4 ms | 28252 KB | Output is correct |
5 | Incorrect | 4 ms | 28248 KB | 3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 | Halted | 0 ms | 0 KB | - |