oj.uz

Submission #1068149

# Submission time Handle Problem Language Result Execution time Memory
1068149 2024-08-21T08:03:21 Z Faisal_Saqib Mechanical Doll (IOI18_doll) C++17
6 / 100
 65 ms 12232 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=4e5+10;
ll cp[NM],final[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;
}
void label_it(vll p)
{
	if(p.size()==1)return;
	vll np;
	for(int i=0;i<p.size();i+=2)
	{
		label++;
		np.pb(-label);
		if(p[i]==-NM)// problem
			p[i]=father_of_all;
		if(p[i+1]==-NM)
			p[i+1]=father_of_all;
		XP.pb(p[i]);
		YP.pb(p[i+1]);
	}
	label_it(np);
}
void create_circuit(int m, std::vector<int> a)
{
	XP.clear();
	YP.clear();
	label=0;
	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]);
	int lps=0;
	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;
			// ll cnt_minus=pw-(ll)child[i].size();
			// for(int j=0,k=0;j<pw;)
			// {
			// 	if(cnt_minus>0)
			// 	{
			// 		cp[j]=-100;
			// 		cp[j+1]=child[i][k];
			// 		k++;
			// 		j+=2;
			// 		cnt_minus--;
			// 	}
			// 	else
			// 	{
			// 		cp[j]=child[i][k];
			// 		k++;
			// 		j++;
			// 	}
			// }
			for(int j=0;j<child[i].size();j++)
				cp[j]=child[i][j];
			for(int j=child[i].size();j<pw;j++)
				cp[j]=-NM;
			vll order=fast_order(pw);
			vll fl(pw);
			for(int j=0;j<pw;j++)
			{
				order[j]--;
				fl[order[j]]=cp[j];
				final[order[j]]=cp[j];
			}
			// cout<<"final: ";
			// for(int j=0;j<pw;j++)
			// 	cout<<final[j]<<' ';
			// cout<<endl;
			// what switches?
			father_of_all=-label-pw+1;
			// pw then
			label_it(fl);
			// cout<<"AT "<<i<<' '<<label<<endl;;
			ans[i]=-label;
		}
		/*
		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]);
		}
		*/
	}
	// cout<<"ans\n";
	// for(int i=0;i<=m;i++)
	// {
	// 	cout<<ans[i]<<' ';
	// }
	// cout<<endl;
	// cout<<"xy\n";
	// for(int i=0;i<label;i++)
	// {
	// 	cout<<XP[i]<<' '<<YP[i]<<endl;
	// }
	answer(ans,XP,YP);
}

Compilation message

doll.cpp: In function 'void label_it(std::vector<int>)':
doll.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0;i<p.size();i+=2)
      |              ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp:71:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |    while(child[i].size()>pw)
      |          ~~~~~~~~~~~~~~~^~~
doll.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    for(int j=0;j<child[i].size();j++)
      |                ~^~~~~~~~~~~~~~~~
doll.cpp:60:6: warning: unused variable 'lps' [-Wunused-variable]
   60 |  int lps=0;
      |      ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 6728 KB Output is correct
3 Correct 14 ms 5588 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 22 ms 8148 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 6728 KB Output is correct
3 Correct 14 ms 5588 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 22 ms 8148 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 35 ms 7880 KB Output is correct
9 Correct 35 ms 9168 KB Output is correct
10 Correct 50 ms 12232 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 6728 KB Output is correct
3 Correct 14 ms 5588 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 22 ms 8148 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 35 ms 7880 KB Output is correct
9 Correct 35 ms 9168 KB Output is correct
10 Correct 50 ms 12232 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 65 ms 11764 KB state 'Y'
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB state 'Y'
2 Halted 0 ms 0 KB -