oj.uz

Submission #1072649

# Submission time Handle Problem Language Result Execution time Memory
1072649 2024-08-24T01:43:03 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
75.6728 / 100
 167 ms 102464 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vll vector<int>
#define ll int
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
vector<int> XP,YP;
const int NM=1e6+10;
ll cp[NM],label=0,father_of_all=-1;
vll fast_order(ll n)
{
    if(n==2)
        return {1,2};
    vll ans;
    ll hn=n/2;
    for(int i=1;i<=n;i+=2)
        ans.pb(i);
    vll hans(hn);
    vll np=fast_order(n/2);
    for(int j=0;j<hn;j++)
        hans[np[j]-1]=ans[j];
    ans.clear();
    for(auto i:hans)
        ans.pb(i);
    for(auto i:hans)
        ans.pb(i+1);
    return ans;
}
vll childx,childy,order_,npp;
int label_it(vll&p,int l,int r,bool lp=0)
{
	if((l-r)==0){
		if(p[l]==-NM)
		{
			return father_of_all;
		}
		return p[l];
	}
	int mid=(l+r)/2;
	bool use=0;
	for(int i=l;i<=r;i++)
	{
		if(p[i]!=-NM)
		{
			use=1;
			break;
		}
	}
	label++;
	int usep=-label;
	int fk=-1;
	if(!use)
	{
		fk=childx.size();
		childx.pb(father_of_all);
		childy.pb(father_of_all);
	}
	else
	{
		int lc=label_it(p,l,mid,1);
		int rc=label_it(p,mid+1,r,1);
		fk=childx.size();
		childx.pb(lc);
		childy.pb(rc);
	}
	order_.pb(fk);
	npp.pb(usep);
	return usep;
}
vll child_[NM];
ll fake_id=0,state[NM],req_sz=0;
int label_it_fake(vll&p,int l,int r,bool lp=0)
{
	if((l-r)==0){
		if(p[l]==-NM)
			return 0;
		req_sz++;
		return -l-1; // always negative
	}
	int mid=(l+r)/2;
	bool use=0;
	for(int i=l;i<=r;i++)
	{
		if(p[i]!=-NM)
		{
			use=1;
			break;
		}
	}
	int fk=fake_id;
	fake_id++;
	child_[fk].clear();
	state[fk]=0;
	if(!use)
	{
		child_[fk].pb(0);
		child_[fk].pb(0);
	}
	else
	{
		int lc=label_it_fake(p,l,mid,1);
		int rc=label_it_fake(p,mid+1,r,1);
		child_[fk].pb(lc);
		child_[fk].pb(rc);
	}
	return fk;
}
vll my_order;
void generate_order(int cur)
{
	if(my_order.size()==req_sz)return;
	if(cur<0)
	{
		my_order.push_back(cur);
		generate_order(0);
		return;
	}
	state[cur]=1-state[cur];
	generate_order(child_[cur][1-state[cur]]);
}
bool check(int m,vector<int> a)
{
	map<int,int> cnt;
	int mx=0;
	for(auto i:a)
	{
		cnt[i]++;
		mx=max(mx,cnt[i]);
	}
	return (mx<=4);
}
void subtask(int m, std::vector<int> a)
{
	vector<int> ans(m+1);
	vector<int> child[m+2];
	vector<int> cur;
	cur.pb(0);
	for(int j=0;j<a.size();j++)
		cur.pb(a[j]);
	cur.pb(0);
	for(int j=1;j<cur.size();j++)
		child[cur[j-1]].push_back(cur[j]);
	vector<int> x,y;
	int s=0;
	for(int i=0;i<=m;i++)
	{
		if(child[i].size()==1)
		{
			ans[i]=child[i][0];
		}
		else if(child[i].size()==2) // solve atmost 2
		{
			// We need
			s++;
			ans[i]=-s;
			x.pb(child[i][0]);
			y.pb(child[i][1]);
		}
		else if(child[i].size()==3)
		{
			int s1=s+1;
			int s2=s+2;
			int s3=s+3;
			s+=3;
			ans[i]=-s1;
			// s1
				x.pb(-s2);
				y.pb(-s3);
			//s2
				x.pb(-s1);
				y.pb(child[i][1]);
			//s3
				x.pb(child[i][0]);
				y.pb(child[i][2]);
		}
		else if(child[i].size()==4)
		{
			int s1=s+1;
			int s2=s+2;
			int s3=s+3;
			s+=3;
			ans[i]=-s1;
			// s1
				x.pb(-s2);
				y.pb(-s3);
			//s2
				x.pb(child[i][0]);
				y.pb(child[i][2]);
			//s3
				x.pb(child[i][1]);
				y.pb(child[i][3]);
		}
	}
	// for(int i=0;i<=m;i++)
	// {
	// 	cout<<ans[i]<<' ';
	// }
	// cout<<endl;
	// for(int i=0;i<s;i++)
	// {
	// 	cout<<x[i]<<' '<<y[i]<<endl;
	// }
	answer(ans,x,y);
}
void create_circuit(int m, std::vector<int> a)
{
	if(check(m,a))
	{
		subtask(m,a);
		return;
	}
	XP.clear();
	YP.clear();
	label=0;
	vector<int> ans(m+1);
	vector<int> child[m+2];
	vector<int> cur;
	int szp=a.size();
	int lg=log2(szp);
	int pw=(1<<lg);
	if(pw==szp)
	{
		int v=a[0];
		child[0].push_back(v);
		for(int j=1;j<a.size();j++)
			child[v].push_back(a[j]);
		child[v].push_back(0);
		int lps=0;
		for(int j=0;j<=m;j++)
			ans[j]=-1;
		for(auto i:{0,v})
		{
			if(child[i].size()==0)continue;
			if(child[i].size()==1)
			{
				ans[i]=child[i][0];
			}
			else
			{
				ll pw=1;
				while(child[i].size()>pw)
					pw*=2;
				int zxp=child[i].size();
				vll fl(pw);
				int cpp=0;
				for(int j=zxp;j<pw;j++)
					fl[cpp]=-NM,cpp++;
				for(int j=0;j<zxp;j++)
					fl[cpp]=child[i][j],cpp++;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				ll og=label;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				req_sz=0;
				my_order.clear();
				fake_id=0;
				int root=label_it_fake(fl,0,pw-1);
				generate_order(root);
				for(int i=0;i<pw;i++)fl[i]=-NM;
				for(int k=0;k<child[i].size();k++)
				{
					fl[-my_order[k]-1]=child[i][k];
				}
				label_it(fl,0,pw-1);
				ll last=XP.size();
				for(int i=0;i<order_.size();i++)
				{
					XP.pb(0);
					YP.pb(0);
				}
				for(int i=0;i<order_.size();i++)
				{
					ll cur=-og-npp[i]-1;
					XP[last+cur]=(childx[i]);
					YP[last+cur]=(childy[i]);
				}
				ans[i]=father_of_all;
			}
		}
		answer(ans,XP,YP);
	}
	else
	{
		cur.pb(0);
		for(int j=0;j<a.size();j++)
			cur.pb(a[j]);
		cur.pb(0);
		for(int j=1;j<cur.size();j++)
			child[cur[j-1]].push_back(cur[j]);
		for(int i=0;i<=m;i++)
		{
			if(child[i].size()==0)continue;
			if(child[i].size()==1)
			{
				ans[i]=child[i][0];
			}
			else
			{
				ll pw=1;
				while(child[i].size()>pw)
					pw*=2;
				int zxp=child[i].size();
				vll fl(pw);
				int cpp=0;
				for(int j=zxp;j<pw;j++)
					fl[cpp]=-NM,cpp++;
				for(int j=0;j<zxp;j++)
					fl[cpp]=child[i][j],cpp++;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				ll og=label;
				father_of_all=-label-1;
				childx.clear();
				childy.clear();
				order_.clear();
				npp.clear();
				req_sz=0;
				my_order.clear();
				fake_id=0;
				int root=label_it_fake(fl,0,pw-1);
				generate_order(root);
				for(int i=0;i<pw;i++)fl[i]=-NM;
				for(int k=0;k<child[i].size();k++)
				{
					fl[-my_order[k]-1]=child[i][k];
				}
				label_it(fl,0,pw-1);
				ll last=XP.size();
				for(int i=0;i<order_.size();i++)
				{
					XP.pb(0);
					YP.pb(0);
				}
				for(int i=0;i<order_.size();i++)
				{
					ll cur=-og-npp[i]-1;
					XP[last+cur]=(childx[i]);
					YP[last+cur]=(childy[i]);
				}
				ans[i]=father_of_all;
			}
		}
		answer(ans,XP,YP);
	}
}

Compilation message

doll.cpp: In function 'void generate_order(int)':
doll.cpp:111:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |  if(my_order.size()==req_sz)return;
      |     ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void subtask(int, std::vector<int>)':
doll.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:141:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:225:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |   for(int j=1;j<a.size();j++)
      |               ~^~~~~~~~~
doll.cpp:241:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  241 |     while(child[i].size()>pw)
      |           ~~~~~~~~~~~~~~~^~~
doll.cpp:267:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:273:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  273 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:278:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:228:7: warning: unused variable 'lps' [-Wunused-variable]
  228 |   int lps=0;
      |       ^~~
doll.cpp:292:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  292 |   for(int j=0;j<a.size();j++)
      |               ~^~~~~~~~~
doll.cpp:295:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  295 |   for(int j=1;j<cur.size();j++)
      |               ~^~~~~~~~~~~
doll.cpp:307:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  307 |     while(child[i].size()>pw)
      |           ~~~~~~~~~~~~~~~^~~
doll.cpp:333:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  333 |     for(int k=0;k<child[i].size();k++)
      |                 ~^~~~~~~~~~~~~~~~
doll.cpp:339:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  339 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~
doll.cpp:344:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  344 |     for(int i=0;i<order_.size();i++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 43 ms 33936 KB Output is correct
3 Correct 44 ms 32288 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 10 ms 30556 KB Output is correct
6 Correct 60 ms 35592 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 43 ms 33936 KB Output is correct
3 Correct 44 ms 32288 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 10 ms 30556 KB Output is correct
6 Correct 60 ms 35592 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 67 ms 35300 KB Output is correct
9 Correct 78 ms 37452 KB Output is correct
10 Correct 114 ms 41012 KB Output is correct
11 Correct 4 ms 26972 KB Output is correct
12 Correct 7 ms 26972 KB Output is correct
13 Correct 4 ms 26972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 43 ms 33936 KB Output is correct
3 Correct 44 ms 32288 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 10 ms 30556 KB Output is correct
6 Correct 60 ms 35592 KB Output is correct
7 Correct 4 ms 27108 KB Output is correct
8 Correct 67 ms 35300 KB Output is correct
9 Correct 78 ms 37452 KB Output is correct
10 Correct 114 ms 41012 KB Output is correct
11 Correct 4 ms 26972 KB Output is correct
12 Correct 7 ms 26972 KB Output is correct
13 Correct 4 ms 26972 KB Output is correct
14 Correct 114 ms 39264 KB Output is correct
15 Correct 62 ms 34268 KB Output is correct
16 Correct 105 ms 37084 KB Output is correct
17 Correct 4 ms 26972 KB Output is correct
18 Correct 4 ms 26972 KB Output is correct
19 Correct 5 ms 26972 KB Output is correct
20 Correct 118 ms 39064 KB Output is correct
21 Correct 4 ms 26968 KB Output is correct
22 Correct 4 ms 26972 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 4 ms 27124 KB Output is correct
4 Correct 4 ms 26968 KB Output is correct
5 Correct 4 ms 27224 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct

Subtask #5
14.7580402392 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 26972 KB Output is partially correct
2 Correct 103 ms 74984 KB Output is correct
3 Partially correct 119 ms 82680 KB Output is partially correct
4 Correct 167 ms 102464 KB Output is correct

Subtask #6
34.914797876 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 26972 KB Output is partially correct
2 Correct 103 ms 74984 KB Output is correct
3 Partially correct 119 ms 82680 KB Output is partially correct
4 Correct 167 ms 102464 KB Output is correct
5 Partially correct 137 ms 41176 KB Output is partially correct
6 Partially correct 119 ms 40584 KB Output is partially correct
7 Partially correct 117 ms 40628 KB Output is partially correct
8 Partially correct 103 ms 39404 KB Output is partially correct
9 Partially correct 85 ms 58700 KB Output is partially correct
10 Partially correct 128 ms 63640 KB Output is partially correct
11 Partially correct 74 ms 37228 KB Output is partially correct
12 Partially correct 49 ms 33752 KB Output is partially correct
13 Correct 130 ms 75848 KB Output is correct
14 Partially correct 75 ms 36204 KB Output is partially correct
15 Partially correct 80 ms 35528 KB Output is partially correct
16 Partially correct 5 ms 27224 KB Output is partially correct
17 Partially correct 52 ms 32780 KB Output is partially correct
18 Correct 105 ms 74992 KB Output is correct
19 Partially correct 46 ms 32976 KB Output is partially correct
20 Partially correct 80 ms 36500 KB Output is partially correct
21 Partially correct 69 ms 35904 KB Output is partially correct
22 Partially correct 76 ms 35896 KB Output is partially correct