oj.uz

Submission #140263

# Submission time Handle Problem Language Result Execution time Memory
140263 2019-08-02T11:44:49 Z bazsi700 Mechanical Doll (IOI18_doll) C++14
100 / 100
 149 ms 12196 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
#define hashA 1257958787
#define hashB 1539500609
#define endl "\n"

vector<pair<int,int> > getorder(int cn) {
	//cout << "a" << endl;
	vector<pair<int,int> > ord;
	ord.push_back({0,0});
	cn/=2;
	while(cn) {
		int n = ord.size();
		//cout << n << endl;
		for(int i = 0; i < n; i++) {
			ord.push_back({ord[i].first+cn,0});
		}
		//cout << cn << endl;
		cn/=2;
	}
	cn = ord.size();
	for(int i = 0; i < cn; i++) {
		ord.push_back({ord[i].first,1});
	}
	return ord;
}


int onpos[20][270000];

void create_circuit(int m, std::vector<int> A) {
	vector<int> C(m+1,-1);
	int n = A.size();
	int cn = 1;
	int ends = 1;
	int layers = 1;
	while(2*ends < n+1) {
		cn*=2;
		cn++;
		ends*= 2;
		layers++;
	}
	onpos[0][0] = 1;
	vector<int> canget(25);
	canget[0] = ends*2;
	for(int i = 1; i < 25; i++) {
		canget[i] = canget[i-1]/2;
	}
	set<pair<int,pair<int,int> > > tobuild;
	tobuild.insert({0,{0,n+1}});
	int currind = 1;
	while(!tobuild.empty()) {
		auto it = tobuild.begin();
		auto nod = *it;
		tobuild.erase(it);
		int lay = nod.first;
		int pos = nod.second.first;
		int want = nod.second.second;
		onpos[lay][pos] = currind++;
		if(lay == layers-1) {
			continue;
		}
		if(canget[lay+1] >= want) {
			tobuild.insert({lay+1,{pos*2+1,want}});
		} else {
			tobuild.insert({lay+1,{pos*2,canget[lay+1]}});
			tobuild.insert({lay+1,{pos*2+1,want-canget[lay+1]}});
		}
	}
	vector<int> X (currind-1);
	vector<int> Y (currind-1);
	for(int lay = 0; lay < layers-1; lay++) {
		for(int i = 0; i < (1<<lay); i++) {
			if(onpos[lay][i]) {
			//	cout << lay << " " << i << " " << onpos[lay][i] << " " << onpos[lay+1][i*2] << " " << onpos[lay+1][i*2+1] << endl;
				if(onpos[lay+1][i*2]) {
					X[onpos[lay][i]-1] = -onpos[lay+1][i*2];
				} else {
					X[onpos[lay][i]-1] = -1;
				}
				if(onpos[lay+1][i*2+1]) {
					Y[onpos[lay][i]-1] = -onpos[lay+1][i*2+1];
				} else {
					Y[onpos[lay][i]-1] = -1;
				}
			}
		}
	}

	/*for(int i = 0; (i+1)*2 < cn; i++) {
		X[i] = -(i*2+2);
		Y[i] = -(i*2+3);
	}*/
	int ind = 0;
	//for(int i = 0; i < currind-1; i++) {
	//	cout << X[i] << " " << Y[i] << endl;
	//}
	//cout << "a" << endl;
	vector<pair<int,int> > ord = getorder(ends);
	//cout << ends << " " << ord.size() << endl;
	int lst = -1;
	for(int i = 0; i < 2*ends; i++) {
		if(onpos[layers-1][ord[i].first]) {
			//cout << ord[i].first << " ";
			//cout << onpos[layers-1][ord[i].first] << endl;
			if(ord[i].second == 0) {
				if(ind < n) {
					X[onpos[layers-1][ord[i].first]-1] = A[ind++];
				} else {
					X[onpos[layers-1][ord[i].first]-1] = -1;
				}
			} else {
				if(ind < n) {
					Y[onpos[layers-1][ord[i].first]-1] = A[ind++];
				} else {
					Y[onpos[layers-1][ord[i].first]-1] = -1;
				}
			}
			lst = onpos[layers-1][ord[i].first]-1;
		}
	}
	Y[lst] = 0;
	/*cout << "b" << endl;
	for(int i = 0; i < currind-1; i++) {
		cout << X[i] << " " << Y[i] << endl;
	}*/
	answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 65 ms 5596 KB Output is correct
3 Correct 47 ms 5216 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 74 ms 7304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 65 ms 5596 KB Output is correct
3 Correct 47 ms 5216 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 74 ms 7304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 94 ms 8868 KB Output is correct
9 Correct 96 ms 9016 KB Output is correct
10 Correct 134 ms 12180 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 65 ms 5596 KB Output is correct
3 Correct 47 ms 5216 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 74 ms 7304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 94 ms 8868 KB Output is correct
9 Correct 96 ms 9016 KB Output is correct
10 Correct 134 ms 12180 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 144 ms 12048 KB Output is correct
15 Correct 90 ms 8744 KB Output is correct
16 Correct 128 ms 12032 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 143 ms 12196 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 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 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 84 ms 8616 KB Output is correct
3 Correct 81 ms 8640 KB Output is correct
4 Correct 132 ms 11800 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 84 ms 8616 KB Output is correct
3 Correct 81 ms 8640 KB Output is correct
4 Correct 132 ms 11800 KB Output is correct
5 Correct 136 ms 11964 KB Output is correct
6 Correct 132 ms 11928 KB Output is correct
7 Correct 129 ms 11924 KB Output is correct
8 Correct 142 ms 11852 KB Output is correct
9 Correct 82 ms 8536 KB Output is correct
10 Correct 135 ms 11800 KB Output is correct
11 Correct 131 ms 11812 KB Output is correct
12 Correct 95 ms 8612 KB Output is correct
13 Correct 85 ms 8704 KB Output is correct
14 Correct 122 ms 8620 KB Output is correct
15 Correct 86 ms 8712 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 90 ms 7456 KB Output is correct
18 Correct 82 ms 8636 KB Output is correct
19 Correct 80 ms 8640 KB Output is correct
20 Correct 149 ms 11800 KB Output is correct
21 Correct 126 ms 11768 KB Output is correct
22 Correct 128 ms 11792 KB Output is correct