oj.uz

Submission #597226

# Submission time Handle Problem Language Result Execution time Memory
597226 2022-07-15T18:01:48 Z Sam_a17 Mechanical Doll (IOI18_doll) C++14
63 / 100
 143 ms 25572 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
const int maxN = 5e5 + 10;
vector<int> adj[maxN];

template<typename T>
void pr(T a) {
  cerr << a << endl;
}

pair<int, int> child[maxN];
pair<bool, bool> valid[maxN];
vector<int> order, low;
int curr = 0, par[maxN], pos = -1;

void build(int h, int node, vector<int>& x, vector<int>& y, int lg) {
  if(h == lg - 1) {
    child[-node].first = curr++;
    child[-node].second = curr++;

    par[curr - 2] = node;
    par[curr - 1] = node;

    low.push_back(node);
  } else {
    child[-node].first = pos - 1;
    child[-node].second = pos - 2;
    
    x.push_back(child[-node].first);
    y.push_back(child[-node].second);

    pos -= 2;

    build(h + 1, child[-node].first, x, y, lg);
    build(h + 1, child[-node].second, x, y, lg);
  }
}

void traverse(int node, int h, int lg) {
  if(h == lg) {
    assert(node >= 0);
    order.push_back(node);
    return;
  }

  traverse(child[-node].first, h + 1, lg);
  swap(child[-node].first, child[-node].second);
}

void create_circuit(int M, std::vector<int> A) {
	int n = sz(A);

  if(n == 1) {
		vector<int> to(M + 1, 1), x, y;
    to[0] = A[0];
    to[A[0]] = 0;

    answer(to, x, y);
    return;
  }

  int maxRep = 0;
	vector<int> rep(M + 1);
	for(int i = 0; i < n; i++) {
		rep[A[i]]++;
		maxRep = max(maxRep, rep[A[i]]);
	}
 
	if(maxRep <= 1) {
		vector<int> to(M + 1, 1), em;
		to[0] = A[0];
		for(int i = 1; i < n; i++) {
			to[A[i - 1]] = A[i];
		} 
		to[A[n - 1]] = 0;
 
		answer(to, em, em);
	} else if( maxRep <= 2) {
		vector<int> to(M + 1, 1), em;
		int s = -1;
		vector<int> X, Y;
		
		A.push_back(0);
		n = sz(A);
		for(int i = 1; i < n; i++) {
			adj[A[i - 1]].push_back(A[i]);
		}
 
		to[0] = A[0];
 
		for(int i = 1; i <= M; i++) {
			if(rep[i] == 2) {
				X.push_back(adj[i][0]);
				Y.push_back(adj[i][1]);
 
				to[i] = s;
				s--;
			} else if(sz(adj[i])) {
				to[i] = adj[i][0];
			}
		}
 
		answer(to, X, Y);
	} else if(maxRep <= 4) {
		A.push_back(0);
		n = sz(A);
 
		vector<int> to(M + 1, 1), em;
		vector<int> X, Y;
		
		for(int i = 1; i < n; i++) {
			adj[A[i - 1]].push_back(A[i]);
		}
 
		to[0] = A[0];
 
		int s = -1;
		for(int i = 1; i <= M; i++) {
      if(sz(adj[i]) == 4) {
				to[i] = s;
				X.push_back(s - 1);
				Y.push_back(s - 2);
 
				X.push_back(adj[i][0]);
				Y.push_back(adj[i][2]);
 
				X.push_back(adj[i][1]);
				Y.push_back(adj[i][3]);
        
        s -= 3;
      } else if(sz(adj[i]) == 3) {
				to[i] = s;
				X.push_back(s - 1);
				Y.push_back(s - 2);
 
				X.push_back(s);
				Y.push_back(adj[i][1]);
 
				X.push_back(adj[i][0]);
				Y.push_back(adj[i][2]);
 
				s -= 3;
			} else if(sz(adj[i]) == 2) {
				to[i] = s;
				// assert(adj[i][0] == adj[i][1]);
				X.push_back(adj[i][0]);
				Y.push_back(adj[i][1]);
				s--;
			} else if(sz(adj[i])) {
				to[i] = adj[i][0];
			}
		}
 
		// for(int i = 0; i <= M; i++) {
		// 	cout << to[i] << " ";
		// } cout << endl;
 
		answer(to, X, Y);
	}	else {
    /*
    if(M == 1) {
      vector<int> ci{1, -1}, X, Y;
      for(int i = 0; i < n; i++) {
        // X.push_back(1);
        // Y.push_back();
      }
  
      // answer(ci, );
    } else {
  
    }*/

    // int cnt = __builtin_popcount(n);
    vector<int> to(M + 1, -1), x, y;
    int logi = log2(n);

    if(n != (1 << logi)) {
      logi++;
    }

    // cout << logi << endl;

    build(0, -1, x, y, logi);

    for(int i = 0; i < (1 << logi); i++) {
      traverse(-1, 0, logi); 
    }

    // for(auto i: order) {
      // cout << i << " ";
    // } cout << endl;

    int power = (1 << logi) - n;
    // cout << "pr:" << power << endl;

    for(int i = 0; i < power; i++) {
      // cout << order[i] << endl;
      if(!valid[-par[order[i]]].first) {
        valid[-par[order[i]]].first = 1;
        child[-par[order[i]]].first = -1;
      } else {
        valid[-par[order[i]]].second = 1;
        child[-par[order[i]]].second = -1;
      }
    }

    A.push_back(0);
    int j = 1;
    for(int i = power; i < (1 << logi); i++) {
      if(!valid[-par[order[i]]].first) {
        valid[-par[order[i]]].first = 1;
        child[-par[order[i]]].first = A[j];
      } else {
        valid[-par[order[i]]].second = 1;
        child[-par[order[i]]].second = A[j];
      }
      j++;
    } 

    for(auto i: low) {
      x.push_back(child[-i].first);
      y.push_back(child[-i].second);
    }

    to[0] = A[0];

    answer(to, x, y);
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 25 ms 14036 KB Output is correct
3 Correct 19 ms 13524 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 16 ms 13548 KB Output is correct
6 Correct 28 ms 14376 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 25 ms 14036 KB Output is correct
3 Correct 19 ms 13524 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 16 ms 13548 KB Output is correct
6 Correct 28 ms 14376 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 50 ms 17852 KB Output is correct
9 Correct 48 ms 18328 KB Output is correct
10 Correct 72 ms 21364 KB Output is correct
11 Correct 8 ms 12052 KB Output is correct
12 Correct 8 ms 11996 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 25 ms 14036 KB Output is correct
3 Correct 19 ms 13524 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 16 ms 13548 KB Output is correct
6 Correct 28 ms 14376 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 50 ms 17852 KB Output is correct
9 Correct 48 ms 18328 KB Output is correct
10 Correct 72 ms 21364 KB Output is correct
11 Correct 8 ms 12052 KB Output is correct
12 Correct 8 ms 11996 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 86 ms 21900 KB Output is correct
15 Correct 59 ms 17856 KB Output is correct
16 Correct 74 ms 19564 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 6 ms 11988 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 79 ms 21004 KB Output is correct
21 Correct 8 ms 11956 KB Output is correct
22 Correct 7 ms 11988 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 11988 KB Output is partially correct
2 Correct 72 ms 19416 KB Output is correct
3 Partially correct 136 ms 24432 KB Output is partially correct
4 Partially correct 130 ms 25084 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 11988 KB Output is partially correct
2 Correct 72 ms 19416 KB Output is correct
3 Partially correct 136 ms 24432 KB Output is partially correct
4 Partially correct 130 ms 25084 KB Output is partially correct
5 Partially correct 134 ms 25572 KB Output is partially correct
6 Partially correct 143 ms 25248 KB Output is partially correct
7 Partially correct 131 ms 25364 KB Output is partially correct
8 Partially correct 131 ms 25068 KB Output is partially correct
9 Partially correct 122 ms 24464 KB Output is partially correct
10 Partially correct 131 ms 25072 KB Output is partially correct
11 Partially correct 126 ms 25048 KB Output is partially correct
12 Partially correct 123 ms 24448 KB Output is partially correct
13 Correct 69 ms 20016 KB Output is correct
14 Partially correct 116 ms 24588 KB Output is partially correct
15 Partially correct 127 ms 24816 KB Output is partially correct
16 Partially correct 9 ms 12500 KB Output is partially correct
17 Correct 76 ms 19652 KB Output is correct
18 Correct 66 ms 19580 KB Output is correct
19 Partially correct 122 ms 24528 KB Output is partially correct
20 Partially correct 124 ms 25084 KB Output is partially correct
21 Partially correct 127 ms 25140 KB Output is partially correct
22 Partially correct 124 ms 24980 KB Output is partially correct