oj.uz

Submission #82344

# Submission time Handle Problem Language Result Execution time Memory
82344 2018-10-30T07:48:51 Z PowerOfNinjaGo Mechanical Doll (IOI18_doll) C++17
70.6719 / 100
 265 ms 14816 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int high;

const int maxn = 8e5+5;

int L[maxn], R[maxn];
vector<int> all, matter;

void build(int cur, int bit, int dep, int to)
{
	// printf("%d ", cur);
	if(dep == high) 
	{
		if(bit&1) R[cur] = -to;
		else L[cur] = -to;
		return;
	}
	if(bit&(1<<(high-dep)))
	{
		R[cur] = cur*2+1;
		build(cur*2+1, bit, dep+1, to);
	}
	else
	{
		L[cur] = cur*2;
		build(cur*2, bit, dep+1, to);
	}
}

bool cmp(int a, int b)
{
	for(int i = 0; i<= high; i++)
	{
		int x = a & (1<<i);
		int y = b & (1<<i);
		if(x != y) return x< y;
	}
}

void create_circuit(int m, vector<int> A)
{
	memset(L, 31, sizeof L);
	memset(R, 31, sizeof R);
	int n = A.size();
	int leaves = n;
	int sig = -1;
	for(int i = 20; i>= 0; i--)
	{
		if((1<<i) & leaves)
		{
			sig = i+1;
			break;
		}
	}
	high = sig;
	for(int i = 0; i< n; i++) all.pb(i);
	all.pb((1<<high)-1);
	sort(all.begin(), all.end(), cmp);
	// printf("%d\n", high);
	for(int i = 0; i<= n; i++)
	{
		// printf("insert %d\n", all[i]);
		build(1, all[i], 1, i< n?A[i]:0);
		// printf("\n"); 
	}
	for(int i = 1; i< (1<<high); i++)
	{
		if(L[i]> 0 && L[i] != 522133279) matter.pb(L[i]);
		if(R[i]> 0 && R[i] != 522133279) matter.pb(R[i]);
	}
	matter.pb(1);
	sort(matter.begin(), matter.end());
	// printf("%d\n", matter.size());
	vector<int> ansx, ansy;
	ansx.resize(matter.size());
	ansy.resize(matter.size());
	vector<int> res(m+1, -1);
	for(int i = 0; i< (int) matter.size(); i++)
	{
		int sw = matter[i];
		// printf("%d: %d %d\n", sw, L[sw], R[sw]);
		if(L[sw]> 0)
		{
			if(L[sw] == 522133279) ansx[i] = -1;
			else ansx[i] = -(lower_bound(matter.begin(), matter.end(), L[sw])-matter.begin()+1);
		}
		else
		{
			ansx[i] = -L[sw];
		}
		if(R[sw]> 0)
		{
			if(R[sw] == 522133279) ansy[i] = -1;
			else ansy[i] = -(lower_bound(matter.begin(), matter.end(), R[sw])-matter.begin()+1);
		}
		else
		{
			ansy[i] = -R[sw];
		}
		// printf("res %d %d\n", ansx[i], ansy[i]);
	}
	answer(res, ansx, ansy);
}

Compilation message

doll.cpp: In function 'bool cmp(int, int)':
doll.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 6548 KB Output is partially correct
2 Correct 134 ms 12328 KB Output is correct
3 Partially correct 129 ms 12348 KB Output is partially correct
4 Partially correct 218 ms 14464 KB Output is partially correct

Subtask #6
45.9139029664 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 6548 KB Output is partially correct
2 Correct 134 ms 12328 KB Output is correct
3 Partially correct 129 ms 12348 KB Output is partially correct
4 Partially correct 218 ms 14464 KB Output is partially correct
5 Partially correct 265 ms 14816 KB Output is partially correct
6 Partially correct 193 ms 14652 KB Output is partially correct
7 Partially correct 200 ms 14668 KB Output is partially correct
8 Partially correct 193 ms 14428 KB Output is partially correct
9 Partially correct 124 ms 12328 KB Output is partially correct
10 Partially correct 190 ms 14464 KB Output is partially correct
11 Partially correct 196 ms 14524 KB Output is partially correct
12 Partially correct 132 ms 12580 KB Output is partially correct
13 Correct 131 ms 12956 KB Output is correct
14 Partially correct 136 ms 13104 KB Output is partially correct
15 Partially correct 131 ms 13244 KB Output is partially correct
16 Partially correct 7 ms 6732 KB Output is partially correct
17 Correct 126 ms 11824 KB Output is correct
18 Correct 134 ms 12584 KB Output is correct
19 Partially correct 129 ms 12584 KB Output is partially correct
20 Partially correct 194 ms 14408 KB Output is partially correct
21 Partially correct 194 ms 14524 KB Output is partially correct
22 Partially correct 198 ms 14424 KB Output is partially correct