oj.uz

답안 #753956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753956 2023-06-06T11:32:56 Z valerikk 자동 인형 (IOI18_doll) C++17
12 / 100
 85 ms 11144 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 4e5 + 501;

int n, m;
int pw;
vector<int> a;
int n1;
int x[N], y[N];
vector<int> kek;
int pos[N], f[N];
int fuck[N];

int dfs(int v) {
	if (n1 == 0) {
		return 1;
	}
	kek.push_back(v);
	if (v < (1 << pw)) {
		y[v] = dfs(2 * v + 1);
		x[v] = dfs(2 * v);
	} else {
		--n1;
	}
	return v;
}

}

void create_circuit(int m1, vector<int> a1) {
	m = m1;
	a = a1;
	n = a.size() + 1;
	a.push_back(0);
	pw = 0;
	while ((1 << pw) < n) {
		++pw;
	}
	vector<int> ord;
	{
		int v = 1;
		while ((int)ord.size() < (1 << pw)) {
			if (v >= (1 << pw)) {
				ord.push_back(v);
				v = 1;
			} else {
				f[v] ^= 1;
				if (f[v]) {
					v = 2 * v;
				} else {
					v = 2 * v + 1;
				}
			}
		}
	}
	assert((int)ord.size() == (1 << pw));
	for (int i = 0; i < (1 << pw); ++i) {
		pos[ord[i]] = i;
	}
	n1 = n;
	dfs(1);
	vector<int> lol, rofl;
	for (int v : kek) {
		if (v < (1 << pw)) {
			lol.push_back(v);
		} else {
			rofl.push_back(v);
		}
	}
	assert((int)rofl.size() == n);
	sort(rofl.begin(), rofl.end(), [&](int v, int u) {
		return pos[v] < pos[u];
	});
	// for (int v : rofl) {
	// 	cout << v << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < n; ++i) {
	// 	cout << a[i] << " ";
	// }
	// cout << endl;
	for (int i = 0; i < n; ++i) {
		fuck[rofl[i]] = a[i];
	}
	vector<int> c(m + 1, -1);
	sort(lol.begin(), lol.end());
	int s = lol.size();
	vector<int> x1(s), y1(s);
	for (int i = 0; i < s; ++i) {
		int v = lol[i];
		// if (i == 3) {
		// 	cout << v << " " << x[v] << " " << y[v] << endl;
		// 	cout << fuck[x[v]] << " " << fuck[y[v]] << endl;
		// }
		if (x[v] >= (1 << pw)) {
			x1[i] = fuck[x[v]];
		} else {
			x1[i] = lower_bound(lol.begin(), lol.end(), x[v]) - lol.begin();
			x1[i] = -(x1[i] + 1);
		}
		if (y[v] >= (1 << pw)) {
			y1[i] = fuck[y[v]];
		} else {
			y1[i] = lower_bound(lol.begin(), lol.end(), y[v]) - lol.begin();
			y1[i] = -(y1[i] + 1);
		}
	}
	answer(c, x1, y1);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 61 ms 8364 KB Output is correct
3 Correct 68 ms 7804 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 85 ms 11144 KB Output is correct
7 Correct 1 ms 320 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 61 ms 8364 KB Output is correct
3 Correct 68 ms 7804 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 85 ms 11144 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Runtime error 57 ms 11012 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 61 ms 8364 KB Output is correct
3 Correct 68 ms 7804 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 85 ms 11144 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Runtime error 57 ms 11012 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 56 ms 10928 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 56 ms 10928 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -