oj.uz

Submission #100755

# Submission time Handle Problem Language Result Execution time Memory
100755 2019-03-14T07:51:50 Z WhipppedCream Mechanical Doll (IOI18_doll) C++17
0 / 100
 1000 ms 6476 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();
	if(n == 1)
	{
		vector<int> fuck(2, 0);
		fuck[0] = A[0];
		answer(fuck, vector<int>(), vector<int>());
		return;
	}
	int leaves = n-1;
	int sig = 0;
	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((1<<high)-i-1);
	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-1?A[i+1]: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);
	res[0] = A[0];
	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 Execution timed out 1093 ms 6476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0.0 / 18.0

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

Subtask #6
0.0 / 56.0

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