oj.uz

Submission #1039996

# Submission time Handle Problem Language Result Execution time Memory
1039996 2024-07-31T13:34:44 Z lovrot Mechanical Doll (IOI18_doll) C++17
10 / 100
 70 ms 14608 KB 
#include "doll.h"
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, int*> pip;

const int N = 2e5 + 10;

int n, m;

int cnt = 0, cntl, rgt[2 * N], lft[2 * N];
vector<int> C, X, Y;
vector<pip> p;

int rec(int k, int l) {
	int u = cnt++, siz = 1 << l;

	if(siz == 2) { 
		if(k == 2) { p.PB({cntl++, &lft[u]}); }
		p.PB({cntl++, &rgt[u]});
//		printf("%d %d %d\n", cntl - 2, cntl - 1, -u - 1);
		return u; 
	}

	if(k <= siz / 2) { 
		lft[u] = -1;
	} else { 
		lft[u] = -(rec(k - siz / 2, l - 1) + 1);
	}
	rgt[u] = -(rec(siz / 2, l - 1) + 1);

	return u;
}

void create_circuit(int mm, vector<int> niz) {
	niz.PB(0);
	n = niz.size();
	m = mm;	
	
	C.resize(m + 1, -1);
	memset(rgt, -1, sizeof(rgt));
	memset(lft, -1, sizeof(lft));

	if(niz.size() & 1) { 
		C[0] = niz[0];
		niz.erase(niz.begin());
		--n;
	}

	int lg = 0;
	for(; (1 << lg) < n; ++lg);

	cntl = (1 << lg) - n;	
	rec(n, lg);

	sort(p.begin(), p.end(), [&lg](pip a, pip b) { 
		for(int i = 0; i <= lg; ++i) { 
			if((a.X & (1 << i)) != (b.X & (1 << i))) {
					return b.X & (1 << i);
			}
		}
		return 0;
	});

	for(int i = 0; i < n; ++i) { 
		*p[i].Y = niz[i];
	}

	X.resize(cnt);
	Y.resize(cnt);
	for(int i = 0; i < cnt; ++i) { 
		X[i] = lft[i];
		Y[i] = rgt[i];
	}

//	for(int i = 0; i < cnt; ++i) { 
//		printf("%d : %d %d\n", -(i + 1), X[i], Y[i]);
//	}
//	for(int i = 0; i < m + 1; ++i) { 
//		printf("%d %d\n", i, C[i]);
//	}
//	debug("bla\n");
	answer(C, X, Y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3328 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3512 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 1 ms 3508 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 3672 KB Output is partially correct
2 Correct 56 ms 11288 KB Output is correct
3 Incorrect 70 ms 14608 KB state 'Y'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 3672 KB Output is partially correct
2 Correct 56 ms 11288 KB Output is correct
3 Incorrect 70 ms 14608 KB state 'Y'
4 Halted 0 ms 0 KB -