oj.uz

답안 #1069509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069509 2024-08-22T04:13:27 Z Faisal_Saqib 자동 인형 (IOI18_doll) C++17
16 / 100
 1000 ms 21572 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],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;
}
vll childx,childy,order_,npp;
int label_it(vll p,int l,int r,bool lp=0)
{
	// cout<<"Range "<<l<<' '<<r<<' '<<" p: ";
	// for(int i=l;i<=r;i++)
	// {
	// 	cout<<p[i]<<' ';
	// }
	// cout<<endl;
	if((l-r)==0){
		// cout<<"Assigned ";
		if(p[l]==-NM)
		{
			// cout<<father_of_all<<endl;
			return father_of_all;
		}
		// cout<<p[l]<<endl;
		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)
	{
		// all minus one is subtree
		// cout<<"Range "<<l<<' '<<r<<endl;
		// cout<<"Child: "<<father_of_all<<' '<<father_of_all<<endl;
		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);
		// cout<<"Range "<<l<<' '<<r<<endl;
		// cout<<"Child: "<<XP.back()<<' '<<YP.back()<<endl;
	}
	// cout<<"Assigned to range "<<l<<' '<<r<<' ';
	// cout<<usep<<endl;
	order_.pb(fk);
	npp.pb(usep);
	return usep;
}
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;
			int zxp=child[i].size(),cpp=0;
			for(int j=zxp;j<pw;j++)
			{
				cp[cpp]=-NM;
				cpp++;
			}
			for(int j=0;j<child[i].size();j++)
			{
				cp[cpp]=child[i][j];
				cpp++;
			}
			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?
			ll og=label;
			father_of_all=-label-1;
			// pw then
			// cout<<"Father "<<father_of_all<<endl;
			// cout<<"Do label\n";
			childx.clear();
			childy.clear();
			order_.clear();
			npp.clear();
			label_it(fl,0,pw-1);
			// cout<<"X: ";
			// for(auto i:childx)
			// {
			// 	cout<<i<<' ';
			// }
			// cout<<endl;
			// cout<<"Y: ";
			// for(auto i:childy)
			// {
			// 	cout<<i<<' ';
			// }
			// cout<<endl;
			// cout<<"Order: ";
			// for(auto i:order_)
			// 	cout<<i<<' ';
			// cout<<endl;
			// cout<<"npp: ";
			// for(auto i:npp)
			// 	cout<<i<<' ';
			// cout<<endl;
			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;
		}
		/*
		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";
	// cout<<XP.size()<<endl;
	// cout<<YP.size()<<endl;
	// for(auto i:XP)
	// {
	// 	cout<<i<<' ';
	// }
	// cout<<endl;
	// for(auto i:YP)
	// {
	// 	cout<<i<<' ';
	// }
	// cout<<endl;
	// for(int i=0;i<label;i++)
	// {
	// 	cout<<XP[i]<<' '<<YP[i]<<endl;
	// }
	answer(ans,XP,YP);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp:111:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |    while(child[i].size()>pw)
      |          ~~~~~~~~~~~~~~~^~~
doll.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    for(int j=0;j<child[i].size();j++)
      |                ~^~~~~~~~~~~~~~~~
doll.cpp:168:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |    for(int i=0;i<order_.size();i++)
      |                ~^~~~~~~~~~~~~~
doll.cpp:173:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |    for(int i=0;i<order_.size();i++)
      |                ~^~~~~~~~~~~~~~
doll.cpp:100:6: warning: unused variable 'lps' [-Wunused-variable]
  100 |  int lps=0;
      |      ^~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 18 ms 7120 KB Output is correct
3 Correct 15 ms 5844 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 24 ms 8916 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 18 ms 7120 KB Output is correct
3 Correct 15 ms 5844 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 24 ms 8916 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 37 ms 10960 KB Output is correct
9 Correct 41 ms 12232 KB Output is correct
10 Correct 61 ms 15644 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 18 ms 7120 KB Output is correct
3 Correct 15 ms 5844 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 24 ms 8916 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 37 ms 10960 KB Output is correct
9 Correct 41 ms 12232 KB Output is correct
10 Correct 61 ms 15644 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 68 ms 15432 KB Output is correct
15 Correct 37 ms 9784 KB Output is correct
16 Correct 54 ms 13044 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 74 ms 15068 KB Output is correct
21 Correct 1 ms 2392 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 2396 KB Output is partially correct
2 Execution timed out 1096 ms 21572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 2396 KB Output is partially correct
2 Execution timed out 1096 ms 21572 KB Time limit exceeded
3 Halted 0 ms 0 KB -