oj.uz

Submission #255323

# Submission time Handle Problem Language Result Execution time Memory
255323 2020-07-31T17:30:39 Z arayi Mechanical Doll (IOI18_doll) C++17
100 / 100
 141 ms 10880 KB 
#include "doll.h"
//Arayi
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>

#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int> 
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;


const int N = 1e6 + 30;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 238;
const ld e = 1e-13;

int n, m, i1 = 1;
vii fp;
vii c, x, y;
bool col[N];
void rec(int v)
{
	if (!col[v])
	{
		col[v] = true;
		if (x[v] == mod)
		{
			x[v] = fp.back();
			fp.pop_back();
			rec(0);
		}
		else if (x[v] < 0) rec(-x[v] - 1);
	}
	else
	{
		col[v] = false;
		if (y[v] == mod)
		{
			y[v] = fp.back();
			fp.pop_back();
			rec(0);
		}
		else if (y[v] < 0) rec(-y[v] - 1);
	}
}
void mk()
{
	vii sm = fp;
	int er = 0;
	while ((1 << er) < n) er++;
	int ss = (1 << er) - n;
	vii nax, nw;
	nax.ad(i1);
	i1++;
	x.ad(mod), y.ad(mod);
	for (int i = 1; i < er; i++)
	{
		for (int j = nax.size() - 1; j >= 0; j--)
		{
			nw.ad(i1);
			y[nax[j] - 1] = -i1, i1++;
			nw.ad(i1);
			x[nax[j] - 1] = -i1, i1++;
			x.ad(mod), x.ad(mod), y.ad(mod), y.ad(mod);
		}
		if (ss & (1 << (er - i)))
		{
			x[nax[0] - 1] = -1;
			i1--;
			x.pop_back();
			y.pop_back();
			nw.pop_back();
		}
		reverse(all(nw));
		swap(nax, nw);
		nw.clear();
	}
	if (ss & 1)
		x[nax[0] - 1] = -1;
	reverse(all(fp));
	rec(0);
}
void create_circuit(int M, vector<int> A) {
	n = A.size();
	m = M;
	c.resize(m + 1);
	c[0] = A[0];
	if (n == 1)
	{
		c[A[0]] = 0;
		answer(c, x, y);
		return;
	}
	for (int i = 1; i <= m; i++)
		c[i] = -1;
	fp = A;
	reverse(all(fp));
	fp.pop_back();
	reverse(all(fp));
	fp.ad(0);
	mk();
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 4316 KB Output is correct
3 Correct 41 ms 4124 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 62 ms 6320 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 4316 KB Output is correct
3 Correct 41 ms 4124 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 62 ms 6320 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 7136 KB Output is correct
9 Correct 81 ms 7696 KB Output is correct
10 Correct 141 ms 10880 KB Output is correct
11 Correct 1 ms 216 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 4316 KB Output is correct
3 Correct 41 ms 4124 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 62 ms 6320 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 75 ms 7136 KB Output is correct
9 Correct 81 ms 7696 KB Output is correct
10 Correct 141 ms 10880 KB Output is correct
11 Correct 1 ms 216 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 115 ms 10392 KB Output is correct
15 Correct 76 ms 6668 KB Output is correct
16 Correct 115 ms 10112 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 138 ms 10644 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 64 ms 5744 KB Output is correct
3 Correct 82 ms 5700 KB Output is correct
4 Correct 107 ms 8724 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 64 ms 5744 KB Output is correct
3 Correct 82 ms 5700 KB Output is correct
4 Correct 107 ms 8724 KB Output is correct
5 Correct 128 ms 9964 KB Output is correct
6 Correct 128 ms 9608 KB Output is correct
7 Correct 114 ms 9756 KB Output is correct
8 Correct 138 ms 9352 KB Output is correct
9 Correct 72 ms 5704 KB Output is correct
10 Correct 111 ms 9276 KB Output is correct
11 Correct 107 ms 8956 KB Output is correct
12 Correct 81 ms 5920 KB Output is correct
13 Correct 72 ms 6284 KB Output is correct
14 Correct 71 ms 6428 KB Output is correct
15 Correct 85 ms 6588 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 90 ms 5912 KB Output is correct
18 Correct 71 ms 5872 KB Output is correct
19 Correct 68 ms 5940 KB Output is correct
20 Correct 109 ms 9156 KB Output is correct
21 Correct 118 ms 9056 KB Output is correct
22 Correct 108 ms 8956 KB Output is correct