oj.uz

Submission #139883

# Submission time Handle Problem Language Result Execution time Memory
139883 2019-08-01T15:27:40 Z almogwald Mechanical Doll (IOI18_doll) C++14
84 / 100
 142 ms 8868 KB 
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
//#include "job.h"
#include "doll.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;

void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	std::vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}

	vector<int> x, y;
	if(N==1){
		x.push_back(-1);
		y.push_back(0);
		answer(C, x, y);
	}
	A.push_back(0);
	int num=0;
	while(1<<num < N){
		num++;
	}
	veci depth,state;
	depth.push_back(num);
	x.push_back(0);
	state.push_back(0);
	y.push_back(0);
	int cur=0;
	int n=N;
	while(depth[cur]>1){
		if(n+(1<<(depth[cur]-1))<=(1<<num)){
			x[cur]=-1;
			n+=1<<(depth[cur]-1);
		}else{
			x[cur]=-(1+x.size());
			depth.push_back(depth[cur]-1);
				x.push_back(0);
				state.push_back(0);
				y.push_back(0);
		}
		y[cur]=-(1+x.size());
					depth.push_back(depth[cur]-1);
						x.push_back(0);
						state.push_back(0);
						y.push_back(0);
						cur++;
	}
	if(n<(1<<num)){
		x[cur]=-1;
	}
	int p=1;
	cur=-1;
	while(p<=N){
		int lcur=-cur-1;
		state[lcur]=1-state[lcur];
		if(state[lcur]){
			lcur=x[lcur];
		}else{
			lcur=y[lcur];
		}
		if(lcur==0){
			lcur=-cur-1;
			if(state[lcur]){
				x[lcur]=A[p++];
			}else{
				y[lcur]=A[p++];
			}
			lcur=-1;
		}
		cur =lcur;
	}
	answer(C, x, y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4300 KB Output is correct
3 Correct 65 ms 4136 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 96 ms 5544 KB Output is correct
7 Incorrect 2 ms 204 KB Wrong Answer: answered not exactly once

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4300 KB Output is correct
3 Correct 65 ms 4136 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 96 ms 5544 KB Output is correct
7 Incorrect 2 ms 204 KB Wrong Answer: answered not exactly once

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 46 ms 4300 KB Output is correct
3 Correct 65 ms 4136 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1356 KB Output is correct
6 Correct 96 ms 5544 KB Output is correct
7 Incorrect 2 ms 204 KB Wrong Answer: answered not exactly once

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 73 ms 6560 KB Output is correct
3 Correct 85 ms 6468 KB Output is correct
4 Correct 116 ms 8572 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 73 ms 6560 KB Output is correct
3 Correct 85 ms 6468 KB Output is correct
4 Correct 116 ms 8572 KB Output is correct
5 Correct 120 ms 8868 KB Output is correct
6 Correct 130 ms 8728 KB Output is correct
7 Correct 137 ms 8656 KB Output is correct
8 Correct 125 ms 8652 KB Output is correct
9 Correct 76 ms 6436 KB Output is correct
10 Correct 118 ms 8600 KB Output is correct
11 Correct 133 ms 8628 KB Output is correct
12 Correct 142 ms 6440 KB Output is correct
13 Correct 80 ms 7072 KB Output is correct
14 Correct 80 ms 6540 KB Output is correct
15 Correct 82 ms 6448 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 75 ms 6832 KB Output is correct
18 Correct 75 ms 6776 KB Output is correct
19 Correct 81 ms 6440 KB Output is correct
20 Correct 117 ms 8588 KB Output is correct
21 Correct 117 ms 8608 KB Output is correct
22 Correct 120 ms 8576 KB Output is correct