Submission #77190

#	Time	Username	Problem	Language	Result	Execution time	Memory
77190		kimjihoon	Mechanical Doll (IOI18_doll)	C++14	100 / 100	179 ms	20816 KiB

doll

#include "doll.h"
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

vector<int> r[100009], st, c, x, y, rx, ry;
vector<pair<int, pair<int, int> > > sq;
int sc = 0, rc = -1, ft;

int vsq(int n, int ts, int te, int t)
{
	if (ts >= te)
		return 0;
	int md = (ts + te) / 2;
	if (n <= md)
		return vsq(n, ts, md, t * 2);
	else
		return vsq(n, md + 1, te, t * 2) + t;
}

int vsq(int n, int tn) 
{
	return vsq(n, 0, tn - 1, 1);
}

int csw(int n, int tn)
{
	sc--;
	int tsc = sc;
	if (ft >= n / 2) {
		ft -= n / 2;
		x[-sc - 1] = -1;
		rc += n / 2;
		if (ft >= n / 2) {
			ft -= n / 2;
			y[-sc - 1] = -1;
			rc += n / 2;
		}
		else {
			if (n == 2) {
				rc++;
				sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 1)));
			}
			else 
				y[-tsc - 1] = csw(n / 2, tn);
		}
		return tsc;
	}
	if (n == 2) {
		rc++;
		sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 0)));
		rc++;
		sq.push_back(make_pair(vsq(rc, tn), make_pair(-sc - 1, 1)));
		return sc;
	}
	int a = csw(n / 2, tn), b = csw(n / 2, tn);
	x[-tsc - 1] = a; y[-tsc - 1] = b;
	return tsc;
}

void create_circuit(int M, std::vector<int> A) {
	A.push_back(0);
	int N = A.size();
	for (int i = 0; i < N - 1; i++)
		r[A[i]].push_back(A[i + 1]);
	for (int i = 0; i < N - 1; i++)
		if (r[A[i]].size() > 1)
			st.push_back(A[i + 1]);
	int t = 1, rn = 0;
	while (t < st.size()) {
		rn += t; t *= 2;
	}
	int rp = t - st.size();
	for (int i = 0; i < rn; i++) {
		x.push_back(100009);
		y.push_back(100009);
	}
	ft = rp;
	if (N > 2 && st.size() > 0) {
		csw(t, t);
		sort(sq.begin(), sq.end());
		for (int i = 0; i < sq.size(); i++) {
			if (sq[i].second.second == 0)
				x[sq[i].second.first] = st[i];
			else
				y[sq[i].second.first] = st[i];
		}	
	}
	c.push_back(A[0]);
	for (int i = 1; i <= M; i++) {
		if (r[i].size() == 0)
			c.push_back(0);
		else if (r[i].size() == 1)
			c.push_back(r[i][0]);
		else
			c.push_back(-1);
	}
	for (int i = 0; i < x.size() && x[i] != 100009; i++)
		rx.push_back(x[i]);
	for (int i = 0; i < y.size() && y[i] != 100009; i++)
		ry.push_back(y[i]);
	answer(c, rx, ry);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  while (t < st.size()) {
      |         ~~^~~~~~~~~~~
doll.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i < sq.size(); i++) {
      |                   ~~^~~~~~~~~~~
doll.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < x.size() && x[i] != 100009; i++)
      |                  ~~^~~~~~~~~~
doll.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i = 0; i < y.size() && y[i] != 100009; i++)
      |                  ~~^~~~~~~~~~

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