Submission #101692

#	Time	Username	Problem	Language	Result	Execution time	Memory
101692		baluteshih	Mechanical Doll (IOI18_doll)	C++14	53 / 100	175 ms	18544 KiB

doll

#include "doll.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> C,X,Y,pl[100005];

int newnode()
{
	X.pb(0),Y.pb(0);
	return -(int)(X.size());
}

int node(vector<int> &v)
{
	if(v.size()==2)
	{
		int tmp=newnode();
		X[-tmp-1]=v[0],Y[-tmp-1]=v[1];
		//cout << "node " << v.size() << " (" << tmp << ")\n";
		//cout << "X:" << X[-tmp-1] << " Y:" << Y[-tmp-1] << "\n"; 
		return tmp;
	}
	vector<int> L,R;
	int tmp=newnode();
	if(v.size()&1)
	{
		L.pb(v[0]),R.pb(tmp);
		for(int i=1;i<v.size();i+=2)
			L.pb(v[i]);
		for(int i=2;i<v.size();i+=2)
			R.pb(v[i]);
	}
	else
	{
		for(int i=0;i<v.size();i+=2)
			L.pb(v[i]);
		for(int i=1;i<v.size();i+=2)
			R.pb(v[i]);
	}
	int a=node(L),b=node(R);
	X[-tmp-1]=a,Y[-tmp-1]=b;
	//cout << "node " << v.size() << " (" << tmp << ")\n";
	//cout << "X:" << X[-tmp-1] << " Y:" << Y[-tmp-1] << "\n"; 
	return tmp;
}

void create_circuit(int M, std::vector<int> A) {
	C.resize(M+1),A.pb(0);
	for(int i=0;i<A.size();++i)
		pl[A[i]].pb(i);
	C[0]=A[0];
	//cout << "success 1\n";
	for(int i=1;i<=M;++i)
		if(pl[i].size()==1)
			C[i]=A[pl[i][0]+1];
		else if(pl[i].size()>1)
		{
			for(int &j:pl[i])
				j=A[j+1];
			C[i]=node(pl[i]);
		}
	//cout << "success 2\n";
	answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'int node(std::vector<int>&)':
doll.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i=1;i<v.size();i+=2)
      |               ~^~~~~~~~~
doll.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=2;i<v.size();i+=2)
      |               ~^~~~~~~~~
doll.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i=0;i<v.size();i+=2)
      |               ~^~~~~~~~~
doll.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=1;i<v.size();i+=2)
      |               ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<A.size();++i)
      |              ~^~~~~~~~~

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