oj.uz

Submission #74905

# Submission time Handle Problem Language Result Execution time Memory
74905 2018-09-07T12:13:42 Z khsoo01 Mechanical Doll (IOI18_doll) C++14
100 / 100
 140 ms 9348 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 200005, G = 18;

int n, m, g, cc = 1;
bool on[G];

vector<int> c, x, y, a[G];

int rev (int I, int S) {
	int R = 0;
	for(int i=1;i<S;i*=2) {
		if(I & i) R += S/2/i;
	}
	return R;
}

void create_circuit (int M, vector<int> A) {
	n = A.size();
	m = M;
	for(int i=1;i-1<n;i*=2) {
		g++;
	}
	for(int i=0;i<g;i++) {
		if(n & (1<<(g-i-1))) on[i] = true;
	}
	for(int i=1,j=0;i<=(1<<g)-1;i++) {
		int T = i ^ (i-1);
		for(int i=g;i--;) {
			if(T & (1<<i)) {
				T = i;
				break;
			}
		}
		if(!on[T]) continue;
		a[T].push_back(A[j++]);
	}
	for(int i=0;i<=m;i++) {
		c.push_back(-1);
	}
	for(int i=0;i<g;i++) {
		if(i == g-1) {
			if(on[i]) x.push_back(a[i][0]);
			else x.push_back(-1);
			y.push_back(0);
		}
		else if(!on[i]) {
			x.push_back(-1);
			y.push_back(-(cc+1));
			cc += 1;
		}
		else {
			int S = (1<<(g-i-1));
			x.push_back(-(cc+1));
			y.push_back(-(cc+S));
			for(int j=1;j<S;j++) {
				if(j < S/2) {
					x.push_back(-(cc+2*j));
					y.push_back(-(cc+2*j+1));
				}
				else {
					x.push_back(a[i][rev(2*(j-S/2), S)]);
					y.push_back(a[i][rev(2*(j-S/2)+1, S)]);
				}
			}
			cc += S;
		}
	}
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 42 ms 4460 KB Output is correct
3 Correct 38 ms 4356 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1488 KB Output is correct
6 Correct 79 ms 5588 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 224 KB Output is correct
2 Correct 42 ms 4460 KB Output is correct
3 Correct 38 ms 4356 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1488 KB Output is correct
6 Correct 79 ms 5588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 79 ms 7052 KB Output is correct
9 Correct 72 ms 7484 KB Output is correct
10 Correct 140 ms 9348 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 204 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 224 KB Output is correct
2 Correct 42 ms 4460 KB Output is correct
3 Correct 38 ms 4356 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1488 KB Output is correct
6 Correct 79 ms 5588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 79 ms 7052 KB Output is correct
9 Correct 72 ms 7484 KB Output is correct
10 Correct 140 ms 9348 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 102 ms 8860 KB Output is correct
15 Correct 95 ms 6652 KB Output is correct
16 Correct 116 ms 8532 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 204 KB Output is correct
20 Correct 98 ms 9028 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 2 ms 204 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 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 80 ms 5508 KB Output is correct
3 Correct 69 ms 5508 KB Output is correct
4 Correct 104 ms 7684 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 80 ms 5508 KB Output is correct
3 Correct 69 ms 5508 KB Output is correct
4 Correct 104 ms 7684 KB Output is correct
5 Correct 109 ms 8380 KB Output is correct
6 Correct 101 ms 8020 KB Output is correct
7 Correct 120 ms 8184 KB Output is correct
8 Correct 101 ms 8528 KB Output is correct
9 Correct 60 ms 5528 KB Output is correct
10 Correct 115 ms 7884 KB Output is correct
11 Correct 96 ms 7604 KB Output is correct
12 Correct 63 ms 5840 KB Output is correct
13 Correct 84 ms 6212 KB Output is correct
14 Correct 77 ms 6400 KB Output is correct
15 Correct 64 ms 6452 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 59 ms 5136 KB Output is correct
18 Correct 72 ms 5744 KB Output is correct
19 Correct 61 ms 5788 KB Output is correct
20 Correct 128 ms 7700 KB Output is correct
21 Correct 95 ms 7640 KB Output is correct
22 Correct 110 ms 7712 KB Output is correct