oj.uz

Submission #423988

# Submission time Handle Problem Language Result Execution time Memory
423988 2021-06-11T15:00:52 Z cfalas Ancient Books (IOI17_books) C++14
12 / 100
 2000 ms 324 KB 
#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
#define len(x) ((int)x.size())

int t, n;
vi a, b;
int s;

vi p;

int d=0;
int dist(int pos, int b, int prev){
	//cout<<d<<endl;
	if(pos<0) return MOD;
	if(pos>=len(p)) return MOD;
	if(d>20) return MOD;
	int done=1;
	FOR(i,len(p)) if(p[i]!=i) done = 0;
	//if(done) cout<<"FOUND\n";
	if(done) return abs(pos-s);
	d++;
	//FOR(i,d) cout<<" |";
	//cout<<pos<<" "<<b<<" | ";
	//FOA(v,p) cout<<v<<" ";
	//cout<<endl;

	int ans=MOD;
	// switch
		int t=p[pos];
		p[pos] = b;
		ans = min(ans, dist(pos, t, -1));
		p[pos] = t;
	if(pos+1!=prev){
		ans = min(ans, 1+dist(pos+1, b, pos));
	}
	if(pos-1!=prev){
		ans = min(ans, 1+dist(pos-1, b, pos));
	}
	d--;
	return ans;
}

long long minimum_walk(std::vector<int> pp, int ss) {
	s = ss;
	p = pp;
	return dist(s,-1, -1);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 264 KB Output is correct
2 Correct 60 ms 204 KB Output is correct
3 Correct 64 ms 276 KB Output is correct
4 Correct 13 ms 288 KB Output is correct
5 Correct 58 ms 264 KB Output is correct
6 Correct 60 ms 204 KB Output is correct
7 Correct 75 ms 204 KB Output is correct
8 Correct 61 ms 272 KB Output is correct
9 Correct 0 ms 248 KB Output is correct
10 Correct 53 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 62 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 60 ms 324 KB Output is correct
16 Correct 62 ms 204 KB Output is correct
17 Correct 62 ms 204 KB Output is correct
18 Correct 58 ms 204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 264 KB Output is correct
2 Correct 60 ms 204 KB Output is correct
3 Correct 64 ms 276 KB Output is correct
4 Correct 13 ms 288 KB Output is correct
5 Correct 58 ms 264 KB Output is correct
6 Correct 60 ms 204 KB Output is correct
7 Correct 75 ms 204 KB Output is correct
8 Correct 61 ms 272 KB Output is correct
9 Correct 0 ms 248 KB Output is correct
10 Correct 53 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 62 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 60 ms 324 KB Output is correct
16 Correct 62 ms 204 KB Output is correct
17 Correct 62 ms 204 KB Output is correct
18 Correct 58 ms 204 KB Output is correct
19 Execution timed out 2063 ms 204 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 264 KB Output is correct
2 Correct 60 ms 204 KB Output is correct
3 Correct 64 ms 276 KB Output is correct
4 Correct 13 ms 288 KB Output is correct
5 Correct 58 ms 264 KB Output is correct
6 Correct 60 ms 204 KB Output is correct
7 Correct 75 ms 204 KB Output is correct
8 Correct 61 ms 272 KB Output is correct
9 Correct 0 ms 248 KB Output is correct
10 Correct 53 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 62 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 60 ms 324 KB Output is correct
16 Correct 62 ms 204 KB Output is correct
17 Correct 62 ms 204 KB Output is correct
18 Correct 58 ms 204 KB Output is correct
19 Execution timed out 2063 ms 204 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 264 KB Output is correct
2 Correct 60 ms 204 KB Output is correct
3 Correct 64 ms 276 KB Output is correct
4 Correct 13 ms 288 KB Output is correct
5 Correct 58 ms 264 KB Output is correct
6 Correct 60 ms 204 KB Output is correct
7 Correct 75 ms 204 KB Output is correct
8 Correct 61 ms 272 KB Output is correct
9 Correct 0 ms 248 KB Output is correct
10 Correct 53 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 62 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 60 ms 324 KB Output is correct
16 Correct 62 ms 204 KB Output is correct
17 Correct 62 ms 204 KB Output is correct
18 Correct 58 ms 204 KB Output is correct
19 Execution timed out 2063 ms 204 KB Time limit exceeded
20 Halted 0 ms 0 KB -