oj.uz

Submission #1040249

# Submission time Handle Problem Language Result Execution time Memory
1040249 2024-07-31T20:04:17 Z lovrot Mechanical Doll (IOI18_doll) C++17
100 / 100
 88 ms 17784 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__)
//#define debug(...) printf("")

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]});
		return u; 
	}

	if(k <= siz / 2) { 
		lft[u] = -1;
	} else { 
		lft[u] = -(rec(k - siz / 2, l - 1) + 1);
	}
	rgt[u] = -(rec(min(k, 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) { 
//		debug("%d : %d %d\n", -(i + 1), X[i], Y[i]);
//	}
//	for(int i = 0; i < m + 1; ++i) { 
//		debug("%d %d\n", i, C[i]);
//	}

	//debug("bla\n");

	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 27 ms 8912 KB Output is correct
3 Correct 26 ms 8508 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 5 ms 4684 KB Output is correct
6 Correct 46 ms 11248 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 27 ms 8912 KB Output is correct
3 Correct 26 ms 8508 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 5 ms 4684 KB Output is correct
6 Correct 46 ms 11248 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 59 ms 12744 KB Output is correct
9 Correct 57 ms 13252 KB Output is correct
10 Correct 81 ms 17784 KB Output is correct
11 Correct 1 ms 3420 KB Output is correct
12 Correct 1 ms 3420 KB Output is correct
13 Correct 1 ms 3416 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 27 ms 8912 KB Output is correct
3 Correct 26 ms 8508 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 5 ms 4684 KB Output is correct
6 Correct 46 ms 11248 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 59 ms 12744 KB Output is correct
9 Correct 57 ms 13252 KB Output is correct
10 Correct 81 ms 17784 KB Output is correct
11 Correct 1 ms 3420 KB Output is correct
12 Correct 1 ms 3420 KB Output is correct
13 Correct 1 ms 3416 KB Output is correct
14 Correct 78 ms 17136 KB Output is correct
15 Correct 50 ms 12220 KB Output is correct
16 Correct 79 ms 16780 KB Output is correct
17 Correct 1 ms 3416 KB Output is correct
18 Correct 1 ms 3420 KB Output is correct
19 Correct 1 ms 3420 KB Output is correct
20 Correct 79 ms 17464 KB Output is correct
21 Correct 1 ms 3416 KB Output is correct
22 Correct 1 ms 3420 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3424 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3420 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 3420 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 46 ms 11216 KB Output is correct
3 Correct 47 ms 11204 KB Output is correct
4 Correct 78 ms 15404 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 46 ms 11216 KB Output is correct
3 Correct 47 ms 11204 KB Output is correct
4 Correct 78 ms 15404 KB Output is correct
5 Correct 80 ms 16680 KB Output is correct
6 Correct 78 ms 16476 KB Output is correct
7 Correct 82 ms 16488 KB Output is correct
8 Correct 76 ms 16148 KB Output is correct
9 Correct 59 ms 11196 KB Output is correct
10 Correct 88 ms 16132 KB Output is correct
11 Correct 77 ms 15656 KB Output is correct
12 Correct 49 ms 11452 KB Output is correct
13 Correct 49 ms 11720 KB Output is correct
14 Correct 55 ms 11964 KB Output is correct
15 Correct 49 ms 12084 KB Output is correct
16 Correct 2 ms 3676 KB Output is correct
17 Correct 48 ms 11424 KB Output is correct
18 Correct 58 ms 11464 KB Output is correct
19 Correct 56 ms 11464 KB Output is correct
20 Correct 78 ms 15908 KB Output is correct
21 Correct 77 ms 15852 KB Output is correct
22 Correct 80 ms 15860 KB Output is correct