Submission #810925

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810925	2023-08-06T17:38:25 Z	WongChun1234	Ancient Books (IOI17_books)	C++14	22 / 100	89 ms	28876 KB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4050,M=1050;
int n,pt,cmx,st,vis[M],par[M],mx[M],mn[M],rrl[M],dist[5][N],lb,rb;
ll ans=LLONG_MAX,cyc;
queue<int> curr[N];
vector<pair<int,int>> adj[2][N];

void addedge(int u,int v,int w){
	adj[0][u].push_back({v,w});
	adj[1][v].push_back({u,w});
}

void build(int id,int l,int r){
	if (l==r){
		rrl[l]=id;
		return;
	}
	int m=(l+r)/2;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	addedge(id,id*2,0);
	addedge(id,id*2+1,0);
}

void modify(int id,int l,int r,int ql,int qr,int v){
	if (l>qr||r<ql) return;
	if (l>=ql&&r<=qr){
		addedge(v,id,0);
		return;
	}
	int m=(l+r)/2;
	modify(id*2,l,m,ql,qr,v);
	modify(id*2+1,m+1,r,ql,qr,v);
}

void bfs(int s,int id,int sav){
	for (int i=0;i<N;i++) dist[sav][i]=N<<2;
	dist[sav][s]=0; curr[0].push(s);
	for (int i=0;i<N;i++){
		while (curr[i].size()){
			int cnde=curr[i].front();
			curr[i].pop();
			for (auto j:adj[id][cnde]) if (dist[sav][cnde]+j.second<dist[sav][j.first]){
				dist[sav][j.first]=dist[sav][cnde]+j.second;
				curr[dist[sav][j.first]].push(j.first);
			}
		}
	}
}

ll minimum_walk(vector<int> p, int s) {
	n=p.size();
	for (int i=0;i<n;i++){
		if (vis[i]) continue;
		par[i]=i; vis[i]=1; mx[i]=mn[i]=i; cyc+=abs(i-p[i]);
		for (int j=p[i];j!=i;j=p[j]) mx[i]=max(mx[i],j),mn[i]=min(mn[i],j),vis[j]=1,par[j]=i,cyc+=abs(j-p[j]);
	}
	//for (int i=0;i<n;i++) cout<<i<<": "<<par[i]<<" "<<mx[i]<<" "<<sz[i]<<"\n";
	memset(vis,0,sizeof(vis));
	build(1,0,n-1);
	for (int i=1;i<=s;i++) addedge(rrl[i],rrl[i-1],1);
	for (int i=s+1;i<n;i++) addedge(rrl[i-1],rrl[i],1);
	for (int i=0;i<n;i++) modify(1,0,n-1,mn[i],mx[i],rrl[i]);
	lb=0,rb=n-1;
	while (p[lb]==lb&&lb<s) lb++;
	while (p[rb]==rb&&rb>s) rb--;
	bfs(rrl[s],0,0);
	bfs(rrl[lb],1,1);
	bfs(rrl[rb],1,2);
	for (int i=0;i<N;i++) ans=min(ans,(ll)dist[0][i]+dist[1][i]+dist[2][i]);
	return cyc+ans*2;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3284 KB	Output is correct
2	Correct	2 ms	3280 KB	Output is correct
3	Correct	2 ms	3204 KB	Output is correct
4	Correct	2 ms	3284 KB	Output is correct
5	Correct	2 ms	3284 KB	Output is correct
6	Correct	2 ms	3224 KB	Output is correct
7	Correct	2 ms	3284 KB	Output is correct
8	Correct	2 ms	3284 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	2 ms	3284 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	2 ms	3220 KB	Output is correct
13	Correct	2 ms	3284 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	2 ms	3284 KB	Output is correct
16	Correct	2 ms	3284 KB	Output is correct
17	Correct	2 ms	3224 KB	Output is correct
18	Correct	2 ms	3284 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3284 KB	Output is correct
2	Correct	2 ms	3280 KB	Output is correct
3	Correct	2 ms	3204 KB	Output is correct
4	Correct	2 ms	3284 KB	Output is correct
5	Correct	2 ms	3284 KB	Output is correct
6	Correct	2 ms	3224 KB	Output is correct
7	Correct	2 ms	3284 KB	Output is correct
8	Correct	2 ms	3284 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	2 ms	3284 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	2 ms	3220 KB	Output is correct
13	Correct	2 ms	3284 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	2 ms	3284 KB	Output is correct
16	Correct	2 ms	3284 KB	Output is correct
17	Correct	2 ms	3224 KB	Output is correct
18	Correct	2 ms	3284 KB	Output is correct
19	Correct	2 ms	3348 KB	Output is correct
20	Correct	3 ms	3412 KB	Output is correct
21	Correct	3 ms	3412 KB	Output is correct
22	Correct	2 ms	3352 KB	Output is correct
23	Correct	2 ms	3412 KB	Output is correct
24	Correct	2 ms	3412 KB	Output is correct
25	Correct	2 ms	3412 KB	Output is correct
26	Correct	2 ms	3412 KB	Output is correct
27	Correct	2 ms	3344 KB	Output is correct
28	Correct	2 ms	3412 KB	Output is correct
29	Correct	2 ms	3352 KB	Output is correct

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3284 KB	Output is correct
2	Correct	2 ms	3280 KB	Output is correct
3	Correct	2 ms	3204 KB	Output is correct
4	Correct	2 ms	3284 KB	Output is correct
5	Correct	2 ms	3284 KB	Output is correct
6	Correct	2 ms	3224 KB	Output is correct
7	Correct	2 ms	3284 KB	Output is correct
8	Correct	2 ms	3284 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	2 ms	3284 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	2 ms	3220 KB	Output is correct
13	Correct	2 ms	3284 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	2 ms	3284 KB	Output is correct
16	Correct	2 ms	3284 KB	Output is correct
17	Correct	2 ms	3224 KB	Output is correct
18	Correct	2 ms	3284 KB	Output is correct
19	Correct	2 ms	3348 KB	Output is correct
20	Correct	3 ms	3412 KB	Output is correct
21	Correct	3 ms	3412 KB	Output is correct
22	Correct	2 ms	3352 KB	Output is correct
23	Correct	2 ms	3412 KB	Output is correct
24	Correct	2 ms	3412 KB	Output is correct
25	Correct	2 ms	3412 KB	Output is correct
26	Correct	2 ms	3412 KB	Output is correct
27	Correct	2 ms	3344 KB	Output is correct
28	Correct	2 ms	3412 KB	Output is correct
29	Correct	2 ms	3352 KB	Output is correct
30	Runtime error	89 ms	28876 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	3412 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3284 KB	Output is correct
2	Correct	2 ms	3280 KB	Output is correct
3	Correct	2 ms	3204 KB	Output is correct
4	Correct	2 ms	3284 KB	Output is correct
5	Correct	2 ms	3284 KB	Output is correct
6	Correct	2 ms	3224 KB	Output is correct
7	Correct	2 ms	3284 KB	Output is correct
8	Correct	2 ms	3284 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	2 ms	3284 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	2 ms	3220 KB	Output is correct
13	Correct	2 ms	3284 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	2 ms	3284 KB	Output is correct
16	Correct	2 ms	3284 KB	Output is correct
17	Correct	2 ms	3224 KB	Output is correct
18	Correct	2 ms	3284 KB	Output is correct
19	Correct	2 ms	3348 KB	Output is correct
20	Correct	3 ms	3412 KB	Output is correct
21	Correct	3 ms	3412 KB	Output is correct
22	Correct	2 ms	3352 KB	Output is correct
23	Correct	2 ms	3412 KB	Output is correct
24	Correct	2 ms	3412 KB	Output is correct
25	Correct	2 ms	3412 KB	Output is correct
26	Correct	2 ms	3412 KB	Output is correct
27	Correct	2 ms	3344 KB	Output is correct
28	Correct	2 ms	3412 KB	Output is correct
29	Correct	2 ms	3352 KB	Output is correct
30	Runtime error	89 ms	28876 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Submission #810925

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 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
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0