70分,TLE求助
查看原帖
70分,TLE求助
357237
Unknown__楼主2022/10/2 08:37
#include <iostream>
#include <set>
#include <algorithm>
#include <cstdio>
#define dit set<int> :: iterator
#define dset set<int>
using namespace std;
dset p0,p1;
int n;
pair<dit,int> check(dset s0,dset s1)
{
	dit it1 = s0.begin(),it2 = s1.begin();
	dit ret;
	int nxt;
	if((*it1) < (*it2))ret = it1,nxt = 1;
	else ret = it2,nxt = 0;
	return make_pair(ret,nxt);
}
void work()
{
	dit it;
	pair<dit,int> p = check(p0,p1);
	int nxt = p.second;
	dit t = p.first;
	printf("%d ",*t);
	if(nxt) p0.erase(*t);
	else p1.erase(*t);
	while(1)
	{
		//cout<<1<<endl;
		if(nxt)
		{
			dit tmp = p1.lower_bound(*t);
			if(tmp == p1.end())break;
			t = tmp;
			printf("%d ",*tmp);
			p1.erase(*tmp);
			nxt = !nxt;
		}
		else 
		{
			dit tmp = p0.lower_bound(*t);
			if(tmp == p0.end())break;
			t = tmp;
			printf("%d ",*tmp);
			p0.erase(*tmp);
			nxt = !nxt;
		}
	}
	printf("\n");
}
int main()
{
	scanf("%d",&n);
	int i;
	for(i = 1;i <= n;i++)
	{
		int op;scanf("%d",&op);
		if(op) p1.insert(i);
		else p0.insert(i);
	}
	while(!p0.empty() || !p1.empty())
	{
		if(p0.empty() || p1.empty())
		{
			if(p0.empty())
			{
				while(!p1.empty())
				{
					dit it = p1.begin();
					printf("%d\n",*it);
					p1.erase(*it);
				}
				return 0;
			}
			else 
			{
				while(!p0.empty())
				{
					dit it = p0.begin();
					printf("%d\n",*it);
					p0.erase(*it);
				}
				return 0;
			}
		}
		else work();
	}
}
2022/10/2 08:37
加载中...