oj.uz

답안 #82138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82138 2018-10-29T08:53:11 Z PowerOfNinjaGo 자동 인형 (IOI18_doll) C++17
37 / 100
 215 ms 16500 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)
{
	if(dep == high) 
	{
		if(bit) R[cur] = -to;
		else L[cur] = -to;
		return;
	}
	if(bit&1)
	{
		R[cur] = cur*2+1;
		build(cur*2+1, bit>>1, dep+1, to);
	}
	else
	{
		L[cur] = cur*2;
		build(cur*2, bit>>1, dep+1, to);
	}
}

bool cmp(int a, int b)
{
	for(int i = high; i>= 0; 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);
	for(int i = 0; i<= n; i++)
	{
		build(1, all[i], 1, i< n?A[i]:0); 
	}
	for(int i = 0; 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());
	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];
		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];
		}
	}
	answer(res, ansx, ansy);
}

Compilation message

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

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 6528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 6528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 6528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 6476 KB Output is partially correct
2 Partially correct 149 ms 15408 KB Output is partially correct
3 Partially correct 151 ms 15404 KB Output is partially correct
4 Partially correct 187 ms 16208 KB Output is partially correct

Subtask #6
28.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 6476 KB Output is partially correct
2 Partially correct 149 ms 15408 KB Output is partially correct
3 Partially correct 151 ms 15404 KB Output is partially correct
4 Partially correct 187 ms 16208 KB Output is partially correct
5 Partially correct 203 ms 16500 KB Output is partially correct
6 Partially correct 189 ms 16340 KB Output is partially correct
7 Partially correct 189 ms 16336 KB Output is partially correct
8 Partially correct 181 ms 16216 KB Output is partially correct
9 Partially correct 151 ms 15540 KB Output is partially correct
10 Partially correct 185 ms 16188 KB Output is partially correct
11 Partially correct 197 ms 16196 KB Output is partially correct
12 Partially correct 178 ms 15400 KB Output is partially correct
13 Partially correct 194 ms 15416 KB Output is partially correct
14 Partially correct 154 ms 15500 KB Output is partially correct
15 Partially correct 155 ms 15528 KB Output is partially correct
16 Partially correct 9 ms 6804 KB Output is partially correct
17 Correct 102 ms 11740 KB Output is correct
18 Partially correct 158 ms 15388 KB Output is partially correct
19 Partially correct 155 ms 15396 KB Output is partially correct
20 Partially correct 215 ms 16204 KB Output is partially correct
21 Partially correct 215 ms 16200 KB Output is partially correct
22 Partially correct 187 ms 16204 KB Output is partially correct