Submission #255231

#	Time	Username	Problem	Language	Result	Execution time	Memory
255231		Abelyan	Mechanical Doll (IOI18_doll)	C++17	100 / 100	134 ms	14744 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

//#pragma GCC target("avx2")
//#pragma GCC optimization("unroll-loops")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=2e6+6;

struct ban{
	int key;
	int* a;
	ban(){}
	ban(int _key,int* _a){
		key=_key;
		a=_a;
	}
	bool operator < (ban other){
		if (key<other.key)return true;
		return false;
	}
};

int n,qan=1,tv=0;
int x[N],y[N];
vector<int> c;
vector<ban> vc;

int cnt=0;
int pw=1,ham=0;

void build(int l,int r,int *pr){
	int sz=(r-l+1);
	
	
	if (sz<=tv){
		tv-=sz;
		*pr=-1;
		return;
	}
	if (l==r){
		//cout<<<endl;
		vc.ad({ham,pr});
		return;
	}
	int md=(l+r)/2;
	int tham=cnt++;
	pw*=2;
	//cout<<l<<" "<<md<<" "<<&x[tham]<<endl;
	build(l,md,&x[tham]);
	ham+=(pw/2);
	build(md+1,r,&y[tham]);
	ham-=(pw/2);
	pw/=2;
	*pr=-(tham+1);
	//cout<<tham+1<<" "<<x[tham]<<" "<<y[tham]<<endl;

}

void create_circuit(int m, vector<int> a) {
	n=a.size();
	c.resize(m+1,-1);
	int nn=n;
	while(nn!=1){
		nn/=2;
		qan++;
	}
	qan=(1<<qan);
	n++;
	tv=qan-n;
	//cout<<tv<<endl;
	int smth;
	build(0,qan-1,&smth);
	sort(all(vc));
	//cout<<1<<endl;
	vector<int> xx,yy;
	
	FOR(i,vc.size()){
		if (i==vc.size()-1)*vc[i].a=0;
		else *vc[i].a=a[i];
	}
	//cout<<vc.size()<<endl;
	//cout<<"--"<<" "<<cnt<<endl;
	FOR(i,cnt){
		//cout<<x[i]<<" "<<y[i]<<endl;
		xx.ad(x[i]);
		yy.ad(y[i]);
	}
	//cout<<2<<endl;
	answer(c,xx,yy);
	
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:14:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i,a) for (int i=0;i<(a);++i)
      |                                ^
doll.cpp:100:2: note: in expansion of macro 'FOR'
  100 |  FOR(i,vc.size()){
      |  ^~~
doll.cpp:101:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if (i==vc.size()-1)*vc[i].a=0;
      |       ~^~~~~~~~~~~~~

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