Submission #1112454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112454		thelegendary08	Mechanical Doll (IOI18_doll)	C++14	11 / 100	70 ms	14816 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) {
	if(M == 1 && A.size() != 1){
		vi v;
		v.pb(0);
		for(auto u : A)v.pb(u);
		v.pb(0);
		int n = v.size() - 2;
		int mx = ceil(log2(n));
		int bts = (1 << mx) - n;
		int num = -1;
		vi x; 
		vi y;
		vi c(M + 1);
		c[0] = 1;
		c[1] = -1;
		f0r(i, mx){
			f0r(j, (1 << i)){
				if(i != mx - 1){
					x.pb(num * 2);
					y.pb(num * 2 - 1);
				}
				else{
					x.pb(1);
					y.pb(1);
				}
				
				num--;
			}
		}
		//cout<<bts<<'\n';
		for(int i = (1 << (mx - 1)); i < (1 << mx) - 1; i++){
			if(bts >= 2){
				x[i - 1] = -1;
				y[i-1] = -1;
				bts -= 2;
			}
			else if(bts == 1){
				x[i-1] = -1;
				bts--;
			}
		}
		y[y.size() - 1] = 0;
		//vout(c);
		//vout(x);
		//vout(y);
		answer(c,x,y);
	}
	else{
		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){
			/*
			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 < nxt[t].size()){
								x.pb(nxt[t][ind1]);
							}
							else{
								x.pb(curnum - 1);
							}
							if(ind2 < nxt[t].size()){
								y.pb(nxt[t][ind2]);
							}
							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;
			}
			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++)
......
   62 |   f0r(i, v.size() - 1){
      |       ~~~~~~~~~~~~~~~             
doll.cpp:62:3: note: in expansion of macro 'f0r'
   62 |   f0r(i, v.size() - 1){
      |   ^~~
doll.cpp:132:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |        if(ind1 < nxt[t].size()){
      |           ~~~~~^~~~~~~~~~~~~~~
doll.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |        if(ind2 < nxt[t].size()){
      |           ~~~~~^~~~~~~~~~~~~~~
doll.cpp:107:9: warning: unused variable 'bts' [-Wunused-variable]
  107 |     int bts = (1 << mx) - nxt[t].size();
      |         ^~~
doll.cpp:109:9: warning: unused variable 'ptr' [-Wunused-variable]
  109 |     int ptr = 0;
      |         ^~~

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