Submission #531754

#	Time	Username	Problem	Language	Result	Execution time	Memory
531754		Servus2022	Mechanical Doll (IOI18_doll)	C++14	0 / 100	60 ms	21376 KiB

doll

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

using namespace std;

constexpr int NMAX = 2e5 + 5;

struct Impart {
	int X, Y;
};

Impart graf[2*NMAX];
int Adanc;
int poz[2*NMAX];
int Coresp[2*NMAX];

vector <int> Ordine;
vector <int> End;

vector <int> C, X, Y;
int Biggest = 0;

void CalculezOrdine (int Adanc) {
	if (Adanc == 0) return;

	int sz = Ordine.size();

    for (int i = 0; i < sz; ++ i ) {
		Ordine.push_back(Ordine[i] * 2);
		Ordine[i] = Ordine.back() - 1;
    }

    CalculezOrdine(Adanc - 1);
}

void Divide (int val, int Adanc) {
	if (Adanc == 0) {
		End.push_back(val);
		Biggest = max(Biggest, val);
		return;
	}

    graf[val].X = 2 * val;
    graf[val].Y = 2 * val + 1;

    Divide(graf[val].X, Adanc-1);
    Divide(graf[val].Y, Adanc-1);
}

void ConstructXandY (int val, int dad = 0, int dir = 0) {
    if (graf[val].X == 0) {

		if (dir == 0) X[dad-1] = Coresp[val];
		else Y[dad-1] = Coresp[val];

		return;
    }

	X[val-1] = -graf[val].X;
	Y[val-1] = -graf[val].Y;

    ConstructXandY(-X[val-1], val, 0);
    ConstructXandY(-Y[val-1], val, 1);
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	N++;
	int Adanc = 0;
	int pow = 1;

	while (pow < N) {
		++ Adanc;
		pow *= 2;
	}
	Divide(1, Adanc);
	Ordine.push_back(1);
	CalculezOrdine(Adanc);

	for (int i = 0; i < Ordine.size(); ++ i )
		poz[Ordine[i]] = End[i];

	for (int i = 0; i <= Biggest; ++ i )
		Coresp[i] = -1;

	for (int i = 0; i < A.size(); ++ i ) {
        Coresp[poz[i+1]] = A[i];
	}

	for (int i = 0; i <= M; ++ i )
		C.push_back(-1);

    Biggest /= 2;
	for (int i = 0; i < Biggest; ++ i ) {
		X.push_back(0);
		Y.push_back(0);
	}

    ConstructXandY(1);
	Y[Biggest-1] = 0;

	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < Ordine.size(); ++ i )
      |                  ~~^~~~~~~~~~~~~~~
doll.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < A.size(); ++ i ) {
      |                  ~~^~~~~~~~~~

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