답안 #581910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581910	2022-06-23T07:59:04 Z	Koosha_mv	고대 책들 (IOI17_books)	C++14	42 / 100	2000 ms	160988 KB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int N=2e6+99;
const ll inf=1e15;
 
int n,vis[N],mx1[N],mx2[N],mn1[N],mn2[N];
ll Max[N],dist[N];
vector<int> vec;
vector<pair<int,int>> g[N];

ll minimum_walk(vector<int> p, int s){
	ll sum=0,ans=0;
	n=p.size();
	int l=n,r=0;
	f(i,0,n){
		sum+=abs(p[i]-i);
		if(p[i]!=i) minm(l,i),maxm(r,i);
	}
	minm(l,s);
	maxm(r,s);
	if(l==r) return 0;
	s-=l;
	f(i,l,r+1) vec.pb(p[i]-l);
	p=vec;
	n=p.size();
	int mx=0;
	l=0,r=n-1;
	f(i,0,s){
		maxm(mx,p[i]);
		if(mx==i){
			ans+=2;
			l=i+1;
		}
	}
	int mn=n;
	f_(i,n-1,s+1){
		minm(mn,p[i]);
		if(mn==i){
			ans+=2;
			r=i-1;
		}
	}
	if(l==r) return sum+ans;
	vec.clear(); s-=l;
	f(i,l,r+1) vec.pb(p[i]-l);
	p=vec;
	n=p.size();
	f(i,0,n){
		g[i].pb({p[i],0});
	}
	f_(i,s,1){
		g[i].pb({i-1,1});
		g[i-1].pb({i,0});
	}
	f(i,s,n-1){
		g[i].pb({i+1,1});
		g[i+1].pb({i,0});
	}
	set<pair<int,int>> Q;
	f(i,0,n){
		dist[i]=(i==s ? 0 : N);
		Q.insert({dist[i],i});
	}
	while(Q.size()){
		int u=(*Q.begin()).S;
		Q.erase(*Q.begin());
		for(auto [v,w] : g[u]){
			if(dist[u]+w<dist[v]){
				Q.erase({dist[v],v});
				dist[v]=dist[u]+w;
				Q.insert({dist[v],v});
			}
		}
	}
	//eror(sum);
	return ans+sum+2ll*dist[0];
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:88:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |   for(auto [v,w] : g[u]){
      |            ^

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47188 KB	Output is correct
2	Correct	25 ms	47220 KB	Output is correct
3	Correct	25 ms	47180 KB	Output is correct
4	Correct	26 ms	47188 KB	Output is correct
5	Correct	30 ms	47204 KB	Output is correct
6	Correct	25 ms	47284 KB	Output is correct
7	Correct	26 ms	47256 KB	Output is correct
8	Correct	25 ms	47248 KB	Output is correct
9	Correct	29 ms	47188 KB	Output is correct
10	Correct	26 ms	47236 KB	Output is correct
11	Correct	28 ms	47152 KB	Output is correct
12	Correct	26 ms	47188 KB	Output is correct
13	Correct	25 ms	47188 KB	Output is correct
14	Correct	28 ms	47188 KB	Output is correct
15	Correct	24 ms	47152 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	27 ms	47216 KB	Output is correct
18	Correct	27 ms	47260 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47188 KB	Output is correct
2	Correct	25 ms	47220 KB	Output is correct
3	Correct	25 ms	47180 KB	Output is correct
4	Correct	26 ms	47188 KB	Output is correct
5	Correct	30 ms	47204 KB	Output is correct
6	Correct	25 ms	47284 KB	Output is correct
7	Correct	26 ms	47256 KB	Output is correct
8	Correct	25 ms	47248 KB	Output is correct
9	Correct	29 ms	47188 KB	Output is correct
10	Correct	26 ms	47236 KB	Output is correct
11	Correct	28 ms	47152 KB	Output is correct
12	Correct	26 ms	47188 KB	Output is correct
13	Correct	25 ms	47188 KB	Output is correct
14	Correct	28 ms	47188 KB	Output is correct
15	Correct	24 ms	47152 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	27 ms	47216 KB	Output is correct
18	Correct	27 ms	47260 KB	Output is correct
19	Correct	31 ms	47436 KB	Output is correct
20	Correct	27 ms	47392 KB	Output is correct
21	Correct	29 ms	47164 KB	Output is correct
22	Correct	26 ms	47292 KB	Output is correct
23	Correct	25 ms	47188 KB	Output is correct
24	Correct	23 ms	47188 KB	Output is correct
25	Correct	24 ms	47248 KB	Output is correct
26	Correct	25 ms	47220 KB	Output is correct
27	Correct	25 ms	47188 KB	Output is correct
28	Correct	25 ms	47244 KB	Output is correct
29	Correct	31 ms	47276 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47188 KB	Output is correct
2	Correct	25 ms	47220 KB	Output is correct
3	Correct	25 ms	47180 KB	Output is correct
4	Correct	26 ms	47188 KB	Output is correct
5	Correct	30 ms	47204 KB	Output is correct
6	Correct	25 ms	47284 KB	Output is correct
7	Correct	26 ms	47256 KB	Output is correct
8	Correct	25 ms	47248 KB	Output is correct
9	Correct	29 ms	47188 KB	Output is correct
10	Correct	26 ms	47236 KB	Output is correct
11	Correct	28 ms	47152 KB	Output is correct
12	Correct	26 ms	47188 KB	Output is correct
13	Correct	25 ms	47188 KB	Output is correct
14	Correct	28 ms	47188 KB	Output is correct
15	Correct	24 ms	47152 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	27 ms	47216 KB	Output is correct
18	Correct	27 ms	47260 KB	Output is correct
19	Correct	31 ms	47436 KB	Output is correct
20	Correct	27 ms	47392 KB	Output is correct
21	Correct	29 ms	47164 KB	Output is correct
22	Correct	26 ms	47292 KB	Output is correct
23	Correct	25 ms	47188 KB	Output is correct
24	Correct	23 ms	47188 KB	Output is correct
25	Correct	24 ms	47248 KB	Output is correct
26	Correct	25 ms	47220 KB	Output is correct
27	Correct	25 ms	47188 KB	Output is correct
28	Correct	25 ms	47244 KB	Output is correct
29	Correct	31 ms	47276 KB	Output is correct
30	Execution timed out	2044 ms	160988 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47376 KB	Output is correct
2	Correct	25 ms	47308 KB	Output is correct
3	Correct	25 ms	47324 KB	Output is correct
4	Correct	25 ms	47272 KB	Output is correct
5	Correct	25 ms	47276 KB	Output is correct
6	Correct	25 ms	47356 KB	Output is correct
7	Correct	25 ms	47316 KB	Output is correct
8	Correct	26 ms	47296 KB	Output is correct
9	Correct	27 ms	47316 KB	Output is correct
10	Correct	27 ms	47240 KB	Output is correct
11	Correct	27 ms	47348 KB	Output is correct
12	Correct	24 ms	47300 KB	Output is correct
13	Correct	25 ms	47360 KB	Output is correct
14	Correct	25 ms	47396 KB	Output is correct
15	Correct	25 ms	47332 KB	Output is correct
16	Correct	26 ms	47384 KB	Output is correct
17	Correct	27 ms	47496 KB	Output is correct
18	Correct	25 ms	47316 KB	Output is correct
19	Correct	31 ms	47380 KB	Output is correct
20	Correct	29 ms	47344 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	47188 KB	Output is correct
2	Correct	25 ms	47220 KB	Output is correct
3	Correct	25 ms	47180 KB	Output is correct
4	Correct	26 ms	47188 KB	Output is correct
5	Correct	30 ms	47204 KB	Output is correct
6	Correct	25 ms	47284 KB	Output is correct
7	Correct	26 ms	47256 KB	Output is correct
8	Correct	25 ms	47248 KB	Output is correct
9	Correct	29 ms	47188 KB	Output is correct
10	Correct	26 ms	47236 KB	Output is correct
11	Correct	28 ms	47152 KB	Output is correct
12	Correct	26 ms	47188 KB	Output is correct
13	Correct	25 ms	47188 KB	Output is correct
14	Correct	28 ms	47188 KB	Output is correct
15	Correct	24 ms	47152 KB	Output is correct
16	Correct	25 ms	47188 KB	Output is correct
17	Correct	27 ms	47216 KB	Output is correct
18	Correct	27 ms	47260 KB	Output is correct
19	Correct	31 ms	47436 KB	Output is correct
20	Correct	27 ms	47392 KB	Output is correct
21	Correct	29 ms	47164 KB	Output is correct
22	Correct	26 ms	47292 KB	Output is correct
23	Correct	25 ms	47188 KB	Output is correct
24	Correct	23 ms	47188 KB	Output is correct
25	Correct	24 ms	47248 KB	Output is correct
26	Correct	25 ms	47220 KB	Output is correct
27	Correct	25 ms	47188 KB	Output is correct
28	Correct	25 ms	47244 KB	Output is correct
29	Correct	31 ms	47276 KB	Output is correct
30	Execution timed out	2044 ms	160988 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

답안 #581910

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 30.0