답안 #581898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581898	2022-06-23T07:50:30 Z	Koosha_mv	고대 책들 (IOI17_books)	C++14	50 / 100	798 ms	116448 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];
queue<int> Q;
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;
	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();
	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-1,0});
	}
	Q.push(s);
	f(i,0,n) dist[i]=(i==s ? 0 : N);
	while(Q.size()){
		int u=Q.front();
		Q.pop();
		for(auto [v,w] : g[u]){
			if(dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;
				Q.push(v);
			}
		}
	}
	//eror(sum);
	return ans+sum+2ll*dist[n-1];
}

Compilation message

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

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47184 KB	Output is correct
2	Correct	23 ms	47204 KB	Output is correct
3	Correct	27 ms	47220 KB	Output is correct
4	Correct	26 ms	47192 KB	Output is correct
5	Correct	25 ms	47168 KB	Output is correct
6	Correct	25 ms	47276 KB	Output is correct
7	Correct	26 ms	47216 KB	Output is correct
8	Correct	26 ms	47284 KB	Output is correct
9	Correct	29 ms	47264 KB	Output is correct
10	Correct	25 ms	47192 KB	Output is correct
11	Correct	24 ms	47188 KB	Output is correct
12	Correct	24 ms	47276 KB	Output is correct
13	Correct	25 ms	47356 KB	Output is correct
14	Correct	23 ms	47188 KB	Output is correct
15	Correct	27 ms	47188 KB	Output is correct
16	Correct	24 ms	47180 KB	Output is correct
17	Correct	24 ms	47248 KB	Output is correct
18	Correct	24 ms	47224 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47184 KB	Output is correct
2	Correct	23 ms	47204 KB	Output is correct
3	Correct	27 ms	47220 KB	Output is correct
4	Correct	26 ms	47192 KB	Output is correct
5	Correct	25 ms	47168 KB	Output is correct
6	Correct	25 ms	47276 KB	Output is correct
7	Correct	26 ms	47216 KB	Output is correct
8	Correct	26 ms	47284 KB	Output is correct
9	Correct	29 ms	47264 KB	Output is correct
10	Correct	25 ms	47192 KB	Output is correct
11	Correct	24 ms	47188 KB	Output is correct
12	Correct	24 ms	47276 KB	Output is correct
13	Correct	25 ms	47356 KB	Output is correct
14	Correct	23 ms	47188 KB	Output is correct
15	Correct	27 ms	47188 KB	Output is correct
16	Correct	24 ms	47180 KB	Output is correct
17	Correct	24 ms	47248 KB	Output is correct
18	Correct	24 ms	47224 KB	Output is correct
19	Correct	24 ms	47316 KB	Output is correct
20	Correct	24 ms	47344 KB	Output is correct
21	Correct	23 ms	47172 KB	Output is correct
22	Correct	24 ms	47192 KB	Output is correct
23	Correct	23 ms	47280 KB	Output is correct
24	Correct	23 ms	47188 KB	Output is correct
25	Correct	25 ms	47216 KB	Output is correct
26	Correct	23 ms	47388 KB	Output is correct
27	Correct	25 ms	47228 KB	Output is correct
28	Correct	29 ms	47228 KB	Output is correct
29	Correct	31 ms	47328 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47184 KB	Output is correct
2	Correct	23 ms	47204 KB	Output is correct
3	Correct	27 ms	47220 KB	Output is correct
4	Correct	26 ms	47192 KB	Output is correct
5	Correct	25 ms	47168 KB	Output is correct
6	Correct	25 ms	47276 KB	Output is correct
7	Correct	26 ms	47216 KB	Output is correct
8	Correct	26 ms	47284 KB	Output is correct
9	Correct	29 ms	47264 KB	Output is correct
10	Correct	25 ms	47192 KB	Output is correct
11	Correct	24 ms	47188 KB	Output is correct
12	Correct	24 ms	47276 KB	Output is correct
13	Correct	25 ms	47356 KB	Output is correct
14	Correct	23 ms	47188 KB	Output is correct
15	Correct	27 ms	47188 KB	Output is correct
16	Correct	24 ms	47180 KB	Output is correct
17	Correct	24 ms	47248 KB	Output is correct
18	Correct	24 ms	47224 KB	Output is correct
19	Correct	24 ms	47316 KB	Output is correct
20	Correct	24 ms	47344 KB	Output is correct
21	Correct	23 ms	47172 KB	Output is correct
22	Correct	24 ms	47192 KB	Output is correct
23	Correct	23 ms	47280 KB	Output is correct
24	Correct	23 ms	47188 KB	Output is correct
25	Correct	25 ms	47216 KB	Output is correct
26	Correct	23 ms	47388 KB	Output is correct
27	Correct	25 ms	47228 KB	Output is correct
28	Correct	29 ms	47228 KB	Output is correct
29	Correct	31 ms	47328 KB	Output is correct
30	Correct	749 ms	116352 KB	Output is correct
31	Correct	798 ms	116448 KB	Output is correct
32	Correct	168 ms	54976 KB	Output is correct
33	Correct	131 ms	59304 KB	Output is correct
34	Correct	128 ms	59228 KB	Output is correct
35	Correct	130 ms	59316 KB	Output is correct
36	Correct	140 ms	59232 KB	Output is correct
37	Correct	128 ms	59232 KB	Output is correct
38	Correct	138 ms	59228 KB	Output is correct
39	Correct	143 ms	59336 KB	Output is correct
40	Correct	125 ms	59768 KB	Output is correct
41	Correct	267 ms	73948 KB	Output is correct
42	Correct	126 ms	59324 KB	Output is correct
43	Correct	732 ms	114348 KB	Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	47184 KB	Output is correct
2	Correct	23 ms	47204 KB	Output is correct
3	Correct	27 ms	47220 KB	Output is correct
4	Correct	26 ms	47192 KB	Output is correct
5	Correct	25 ms	47168 KB	Output is correct
6	Correct	25 ms	47276 KB	Output is correct
7	Correct	26 ms	47216 KB	Output is correct
8	Correct	26 ms	47284 KB	Output is correct
9	Correct	29 ms	47264 KB	Output is correct
10	Correct	25 ms	47192 KB	Output is correct
11	Correct	24 ms	47188 KB	Output is correct
12	Correct	24 ms	47276 KB	Output is correct
13	Correct	25 ms	47356 KB	Output is correct
14	Correct	23 ms	47188 KB	Output is correct
15	Correct	27 ms	47188 KB	Output is correct
16	Correct	24 ms	47180 KB	Output is correct
17	Correct	24 ms	47248 KB	Output is correct
18	Correct	24 ms	47224 KB	Output is correct
19	Correct	24 ms	47316 KB	Output is correct
20	Correct	24 ms	47344 KB	Output is correct
21	Correct	23 ms	47172 KB	Output is correct
22	Correct	24 ms	47192 KB	Output is correct
23	Correct	23 ms	47280 KB	Output is correct
24	Correct	23 ms	47188 KB	Output is correct
25	Correct	25 ms	47216 KB	Output is correct
26	Correct	23 ms	47388 KB	Output is correct
27	Correct	25 ms	47228 KB	Output is correct
28	Correct	29 ms	47228 KB	Output is correct
29	Correct	31 ms	47328 KB	Output is correct
30	Correct	749 ms	116352 KB	Output is correct
31	Correct	798 ms	116448 KB	Output is correct
32	Correct	168 ms	54976 KB	Output is correct
33	Correct	131 ms	59304 KB	Output is correct
34	Correct	128 ms	59228 KB	Output is correct
35	Correct	130 ms	59316 KB	Output is correct
36	Correct	140 ms	59232 KB	Output is correct
37	Correct	128 ms	59232 KB	Output is correct
38	Correct	138 ms	59228 KB	Output is correct
39	Correct	143 ms	59336 KB	Output is correct
40	Correct	125 ms	59768 KB	Output is correct
41	Correct	267 ms	73948 KB	Output is correct
42	Correct	126 ms	59324 KB	Output is correct
43	Correct	732 ms	114348 KB	Output is correct
44	Incorrect	30 ms	47232 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3306'
45	Halted	0 ms	0 KB	-

답안 #581898

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0