Submission #1112469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112469		thelegendary08	Mechanical Doll (IOI18_doll)	C++14	53 / 100	82 ms	16056 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define vvi vector<vector<int>>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
using namespace std;
void create_circuit(int M, std::vector<int> A) {
	vi v;
	v.pb(0);
	for(auto u : A)v.pb(u);
	v.pb(0);
	vvi nxt(M+1);
	f0r(i, v.size() - 1){
		nxt[v[i]].pb(v[i+1]);
	}
	int curnum = 0;
	vi c(M+1);
	vi x;
	vi y;
	//f0r(t, M+1)cout<<nxt[t].size()<<' ';
	//cout<<'\n';
	f0r(t, M+1){
		/*
		if(nxt[i].size() == 1){
			c[i] = nxt[i][0];
		}
		else if(nxt[i].size() == 2){
			c[i] = num;
			x.pb(nxt[i][0]);
			y.pb(nxt[i][1]);
			num--;
		}
		else if(nxt[i].size() == 3){
			c[i] = num;
			x.pb(num-1);
			y.pb(num - 2);
			num--;
			x.pb(nxt[i][0]);
			y.pb(nxt[i][1]);
			num--;
			x.pb(c[i]);
			y.pb(nxt[i][2]);
			num--;
		}
		else if(nxt[i].size() == 4){
			c[i] = num;
			x.pb(num-1);
			y.pb(num - 2);
			num--;
			x.pb(nxt[i][0]);
			y.pb(nxt[i][2]);
			num--;
			x.pb(nxt[i][1]);
			y.pb(nxt[i][3]);
			num--;
		}
		*/
		if(nxt[t].size() >= 2){
			int mx = ceil(log2(nxt[t].size()));
			int bts = (1 << mx) - nxt[t].size();
			int num = -1;
			int ptr = 0;
			c[t] = curnum - 1;
			
			f0r(i, mx){
				f0r(j, (1 << i)){
					if(i != mx - 1){
						x.pb(curnum + num * 2);
						y.pb(curnum + num * 2 - 1);
					}
					else{
						int ind1;
						int nind = j*2;
						ind1 = 0;
						for(int k = mx-1; k>=0; k--){
							ind1 += (1 << (mx -1- k)) * (((1 << k) & nind) > 0);
						}
						//cout<<nind<<' '<<ind1<<'\n';
						int nind2 = j*2 + 1;
						int ind2 = 0;
						for(int k = mx; k>=0; k--){
							ind2 += (1 << (mx -1- k)) * (((1 << k) & nind2) > 0);
						}
						//cout<<nind2<<' '<<ind2<<'\n';
						if(ind1 >= bts){
							x.pb(nxt[t][ind1 - bts]);
						}
						else{
							x.pb(curnum - 1);
						}
						if(ind2 >= bts){
							y.pb(nxt[t][ind2 - bts]);
						}
						else{
							y.pb(curnum - 1);
						}
					}
					
					num--;
				}
			}
			//cout<<bts<<'\n';
			/*
			for(int i = (1 << (mx - 1)); i < (1 << mx) - 1; i++){
				if(bts >= 2){
					x[curnum + i - 1] = curnum-1;
					y[curnum + i-1] = curnum-1;
					bts -= 2;
				}
				else if(bts == 1){
					x[curnum + i-1] = curnum-1;
					bts--;
				}
			}
			*/
			//y[y.size() - 1] = 0;
			curnum += num + 1;
		}
		else if(nxt[t].size() == 1){
			c[t] = nxt[t][0];
		}
		
	}
	//vout(c);
	//vout(x);
	//vout(y);
	answer(c,x,y);
	
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:6:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define f0r(i,n) for(int i = 0; i<n; i++)
......
   15 |  f0r(i, v.size() - 1){
      |      ~~~~~~~~~~~~~~~              
doll.cpp:15:2: note: in expansion of macro 'f0r'
   15 |  f0r(i, v.size() - 1){
      |  ^~~
doll.cpp:64:8: warning: unused variable 'ptr' [-Wunused-variable]
   64 |    int ptr = 0;
      |        ^~~

• 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