Submission #785883

#	Time	Username	Problem	Language	Result	Execution time	Memory
785883		esomer	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	195 ms	57132 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"

using namespace std;

typedef long long ll;

vector<int> X, Y;
vector<set<int>> which;
map<int, int> mp;
vector<int> vis;

int id;

void DFS(int curr, int add, vector<int>& adj, int org){
	if(add >= (int)adj.size()){
		if(id < (int)adj.size()){
			id++; 
			vis.push_back(curr);
		}
		return;
	}
	int ind = (int)X.size();
	DFS(curr + add, add * 2, adj, org);
	DFS(curr, add * 2, adj, org);
}

int DFS2(int curr, int add, vector<int>& adj, int org){
	if(add >= (int)adj.size()){
		bool gd = mp.count(curr);
		if(gd) return mp[curr];
		else return org;
	}
	int ind = (int)X.size();
	X.push_back(-1);
	Y.push_back(-1);
	which.push_back({});
	if(org == 0) org = -(ind+1);
	Y[ind] = DFS2(curr + add, add * 2, adj, org);
	X[ind] = DFS2(curr, add * 2, adj, org);
	//~ cout << "ind " << ind << endl;
	if(X[ind] >= 0 || X[ind] == org) which[ind].insert(X[ind]);
	else{
		//~ cout << "X[ind] " << X[ind] << endl;
		int t = 0;
		for(auto x : which[-X[ind] - 1]){
			if(t == 2) break;
			t++;
			which[ind].insert(x);
		}
	}
	if(Y[ind] >= 0 || Y[ind] == org) which[ind].insert(Y[ind]);
	else{
		//~ cout << "Y[ind] " << Y[ind] << endl;
		int t = 0;
		for(auto x : which[-Y[ind] - 1]){
			if(t == 2) break;
			t++;
			which[ind].insert(x);
		}
	}
	if((int)which[ind].size() == 1){
		X.pop_back();
		Y.pop_back();
		int val = *which[ind].begin();
		which.pop_back();
		return val;
	}
	return -(ind+1);
}

void create_circuit(int M, vector<int> A){
	int m = M;
	int n = (int)A.size();
	vector<int> c(m+1, -1);
	A.push_back(0);
	c[0] = A[0];
	vector<vector<int>> adj(M + 1);
	for(int i = 0; i < n; i++){
		adj[A[i]].push_back(A[i+1]);
	}
	for(int i = 1; i <= M; i++){
		if((int)adj[i].size() == 0){
			c[i] = i;
			continue;
		}
		id = 0;
		mp.clear();
		vis.clear();
		DFS(0, 1, adj[i], 0);
		sort(vis.begin(), vis.end());
		for(int j = 0; j < (int)vis.size(); j++){
			mp[vis[j]] = adj[i][j];
		}
		c[i] = DFS2(0, 1, adj[i], 0);
	}
	//~ for(int i = 0; i <= m; i++){
		//~ cout << "i " << i << " c " << c[i] << endl;
	//~ }
	//~ for(int i = 0; i < (int)X.size(); i++){
		//~ cout << "s " << -(i+1) << " x " << X[i] << " y " << Y[i] << endl;
	//~ }
	answer(c, X, Y);
}
//~ namespace {

//~ constexpr int P_MAX = 20000000;
//~ constexpr int S_MAX = 400000;

//~ int M, N;
//~ std::vector<int> A;

//~ bool answered;
//~ int S;
//~ std::vector<int> IC, IX, IY;

//~ int read_int() {
  //~ int x;
  //~ if (scanf("%d", &x) != 1) {
    //~ fprintf(stderr, "Error while reading input\n");
    //~ exit(1);
  //~ }
  //~ return x;
//~ }

//~ void wrong_answer(const char *MSG) {
  //~ printf("Wrong Answer: %s\n", MSG);
  //~ exit(0);
//~ }

//~ void simulate() {
  //~ if (S > S_MAX) {
    //~ char str[50];
    //~ sprintf(str, "over %d switches", S_MAX);
    //~ wrong_answer(str);
  //~ }
  //~ for (int i = 0; i <= M; ++i) {
    //~ if (!(-S <= IC[i] && IC[i] <= M)) {
      //~ wrong_answer("wrong serial number");
    //~ }
  //~ }
  //~ for (int j = 1; j <= S; ++j) {
    //~ if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
      //~ wrong_answer("wrong serial number");
    //~ }
    //~ if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
      //~ wrong_answer("wrong serial number");
    //~ }
  //~ }

  //~ int P = 0;
  //~ std::vector<bool> state(S + 1, false);
  //~ int pos = IC[0];
  //~ int k = 0;
  //~ FILE *file_log = fopen("log.txt", "w");
  //~ fprintf(file_log, "0\n");
  //~ for (;;) {
    //~ fprintf(file_log, "%d\n", pos);
    //~ if (pos < 0) {
      //~ if (++P > P_MAX) {
        //~ fclose(file_log);
        //~ char str[50];
        //~ sprintf(str, "over %d inversions", P_MAX);
        //~ wrong_answer(str);
      //~ }
      //~ state[-pos] = !state[-pos];
      //~ pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
    //~ } else {
      //~ if (pos == 0) {
        //~ break;
      //~ }
      //~ if (k >= N) {
        //~ fclose(file_log);
        //~ wrong_answer("wrong motion");
      //~ }
      //~ if (pos != A[k++]) {
        //~ fclose(file_log);
        //~ wrong_answer("wrong motion");
      //~ }
      //~ pos = IC[pos];
    //~ }
  //~ }
  //~ fclose(file_log);
  //~ if (k != N) {
    //~ wrong_answer("wrong motion");
  //~ }
  //~ for (int j = 1; j <= S; ++j) {
    //~ if (state[j]) {
      //~ wrong_answer("state 'Y'");
    //~ }
  //~ }
  //~ printf("Accepted: %d %d\n", S, P);
//~ }

//~ }  // namespace

//~ void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
  //~ if (answered) {
    //~ wrong_answer("answered not exactly once");
  //~ }
  //~ answered = true;
  //~ // check if input format is correct
  //~ if ((int)C.size() != M + 1) {
    //~ wrong_answer("wrong array length");
  //~ }
  //~ if (X.size() != Y.size()) {
    //~ wrong_answer("wrong array length");
  //~ }
  //~ S = X.size();
  //~ IC = C;
  //~ IX = X;
  //~ IY = Y;
//~ }

//~ int main() {
  //~ M = read_int();
  //~ N = read_int();
  //~ A.resize(N);
  //~ for (int k = 0; k < N; ++k) {
    //~ A[k] = read_int();
  //~ }

  //~ answered = false;
  //~ create_circuit(M, A);
  //~ if (!answered) {
    //~ wrong_answer("answered not exactly once");
  //~ }
  //~ FILE *file_out = fopen("out.txt", "w");
  //~ fprintf(file_out, "%d\n", S);
  //~ for (int i = 0; i <= M; ++i) {
    //~ fprintf(file_out, "%d\n", IC[i]);
  //~ }
  //~ for (int j = 1; j <= S; ++j) {
    //~ fprintf(file_out, "%d %d\n", IX[j - 1], IY[j - 1]);
  //~ }
  //~ fclose(file_out);
  //~ simulate();
  //~ return 0;
//~ }

Compilation message (stderr)

doll.cpp: In function 'void DFS(int, int, std::vector<int>&, int)':
doll.cpp:23:6: warning: unused variable 'ind' [-Wunused-variable]
   23 |  int ind = (int)X.size();
      |      ^~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 41.553352349600004 / 56