oj.uz

답안 #739812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739812 2023-05-11T10:53:27 Z sentheta 자동 인형 (IOI18_doll) C++17
100 / 100
 115 ms 14376 KB 
#include "doll.h"
#include<vector>
#include<algorithm>
#include<utility>
#include<array>
#include<map>
#include<set>
#include<cassert>
#include<iostream>
using namespace std;
#define V vector
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define nl '\n'
#define _ << " " <<
#define dbg(x) cout << "?" << #x << " : " << x << endl;

const int N = 4e5+5;
const int B = 3;

int n, m;
V<int> a;
V<int> c, lc, rc;
int make(){
	lc.push_back(-1);
	rc.push_back(-1);
	return -(int)lc.size();
}
int f(int x){
	return -x-1;
}



V<int> leaves;
bool stat[N];

void create_circuit(int _m,V<int> _a){
	a.swap(_a); a.push_back(0);
	n = a.size(); m = _m;


	// build tree
	V<int> v(n,0);
	while(v.size() > 1){
		V<int> nxt;

		if(v.size()%2==1){
			int x=1, y=v[0];

			int z = make();
			lc[f(z)] = x; rc[f(z)] = y;
			nxt.push_back(z);
		}

		for(int i=v.size()%2; i<(int)v.size(); i+=2){
			int x=v[i], y=v[i+1];

			int z = make();
			lc[f(z)] = x; rc[f(z)] = y;
			nxt.push_back(z);
		}

		v.swap(nxt);
	}

	for(int x=-1; ; x--){
		int idx = -x-1;
		if(lc[idx]==1) lc[idx] = -lc.size();
		if(rc[idx]==1) rc[idx] = -rc.size();

		// cout << x _ lc[idx] _ rc[idx] << nl;
		if(x==-(int)lc.size()) break;
	}
	c = V<int>(m+1, -lc.size());

	// return;



	// simulate to find order of leaves
	// dbg("LEAVES");
	int x = -lc.size();
	while((int)leaves.size() < n){
		// dbg(x);
		int idx = -x-1, y;
		if(stat[idx]==0) y = lc[idx];
		else y = rc[idx];
		stat[idx] ^= 1;

		if(y==0){
			// cout << "LEAF" << nl;
			// dbg(x);
			leaves.push_back(x);
			x = -lc.size();
		}
		else{
			x = y;
		}
	}
	rep(i,0,N) stat[i] = 0;

	rep(i,0,n){
		x = leaves[i];
		int idx = -x-1;

		if(lc[idx]==0){
			lc[idx] = a[i];
		}
		else{
			rc[idx] = a[i];
		}
	}



	answer(c,lc,rc);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 43 ms 6212 KB Output is correct
3 Correct 38 ms 5788 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 10 ms 1844 KB Output is correct
6 Correct 58 ms 8100 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 43 ms 6212 KB Output is correct
3 Correct 38 ms 5788 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 10 ms 1844 KB Output is correct
6 Correct 58 ms 8100 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 76 ms 9944 KB Output is correct
9 Correct 85 ms 10512 KB Output is correct
10 Correct 115 ms 14376 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 43 ms 6212 KB Output is correct
3 Correct 38 ms 5788 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 10 ms 1844 KB Output is correct
6 Correct 58 ms 8100 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 76 ms 9944 KB Output is correct
9 Correct 85 ms 10512 KB Output is correct
10 Correct 115 ms 14376 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 113 ms 13360 KB Output is correct
15 Correct 70 ms 9124 KB Output is correct
16 Correct 108 ms 12944 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 110 ms 13572 KB Output is correct
21 Correct 1 ms 608 KB Output is correct
22 Correct 1 ms 596 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 688 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 67 ms 8456 KB Output is correct
3 Correct 64 ms 8388 KB Output is correct
4 Correct 102 ms 11836 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 67 ms 8456 KB Output is correct
3 Correct 64 ms 8388 KB Output is correct
4 Correct 102 ms 11836 KB Output is correct
5 Correct 105 ms 12960 KB Output is correct
6 Correct 103 ms 12776 KB Output is correct
7 Correct 104 ms 12816 KB Output is correct
8 Correct 101 ms 12552 KB Output is correct
9 Correct 67 ms 8552 KB Output is correct
10 Correct 100 ms 12452 KB Output is correct
11 Correct 97 ms 12200 KB Output is correct
12 Correct 70 ms 8692 KB Output is correct
13 Correct 68 ms 8952 KB Output is correct
14 Correct 71 ms 9068 KB Output is correct
15 Correct 68 ms 9120 KB Output is correct
16 Correct 2 ms 960 KB Output is correct
17 Correct 61 ms 8172 KB Output is correct
18 Correct 64 ms 8684 KB Output is correct
19 Correct 65 ms 8704 KB Output is correct
20 Correct 100 ms 12468 KB Output is correct
21 Correct 97 ms 12216 KB Output is correct
22 Correct 98 ms 12168 KB Output is correct