Submission #243640

#	Time	Username	Problem	Language	Result	Execution time	Memory
243640		TadijaSebez	RLE (BOI06_rle)	C++11	90 / 100	2598 ms	117132 KiB

rle

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=100050;
const int M=2000050;
int a[M],n,m;
vector<pair<int,ll>> seq;
void push(int x, ll sz)
{
	if(seq.size() && seq.back().first==x) seq[seq.size()-1].second+=sz;
	else seq.pb({x,sz});
}
void Decrypt()
{
	int key=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i]==key)
		{
			if(a[i+1]==key)
			{
				push(a[i+1],a[i+2]+1);
			}
			else
			{
				if(a[i+2]==0) key=a[i+1];
				else push(a[i+1],a[i+2]+3);
			}
			i+=2;
		}
		else push(a[i],1);
	}
}
vector<pair<int,set<int>>> groups;
void Check()
{
	for(int i=0;i<groups.size();i++)
	{
		if(groups[i].second.empty())
		{
			swap(groups[i],groups[groups.size()-1]);
			groups.pop_back();
			return;
		}
	}
}
unordered_map<int,int> change[N];
vector<int> ans;
int Calc1(ll sz)
{
	int cnt=0;
	while(sz>0)
	{
		cnt+=3;
		sz-=n;
	}
	return cnt;
}
int Calc2(ll sz)
{
	int cnt=0;
	while(sz>0)
	{
		if(sz<=3) cnt+=sz;
		else cnt+=3;
		sz-=n+2;
	}
	return cnt;
}
void Solve()
{
	groups.pb({0,{0}});
	set<int> tmp;
	for(int i=1;i<n;i++) tmp.insert(i),change[i][-1]=0;
	groups.pb({3,tmp});
	for(int tm=0;tm<seq.size();tm++)
	{
		int x=seq[tm].first;
		ll sz=seq[tm].second;
		//printf("(%i %i) ",x,sz);
		int dp;
		for(int i=0;i<groups.size();i++)
		{
			if(groups[i].second.count(x))
			{
				dp=groups[i].first;
				groups[i].second.erase(x);
				if(groups[i].second.empty()){
					for(int j=i+1;j<groups.size();j++)groups[j-1]=groups[j];
					groups.pop_back();
				}
			}
		}
		Check();
		int c1=Calc1(sz);
		int c2=Calc2(sz);
		int mn=0;
		for(int i=0;i<groups.size();i++)
		{
			groups[i].first+=c2;
			if(i==0 || groups[mn].first>groups[i].first) mn=i;
		}
		if(groups[mn].first+3<dp+c1)
		{
			change[x][tm]=*groups[mn].second.begin();
			dp=groups[mn].first+3;
		}
		else dp+=c1;
		bool ok=0;
		for(int i=0;i<groups.size();i++) if(groups[i].first==dp)
		{
			groups[i].second.insert(x);
			ok=1;
			break;
		}
		if(!ok) groups.pb({dp,{x}});
	}
}
void Add(int key, int x, ll sz)
{
	while(sz>0)
	{
		if(key==x)
		{
			int l=min(sz,(ll)n);
			ans.pb(l-1);
			ans.pb(x);
			ans.pb(key);
			sz-=l;
		}
		else
		{
			if(sz<=3)
			{
				while(sz--) ans.pb(x);
			}
			else
			{
				int l=min(sz,(ll)n+2);
				ans.pb(l-3);
				ans.pb(x);
				ans.pb(key);
				sz-=l;
			}
		}
	}
}
void ChangeKey(int x, int y)
{
	ans.pb(0);
	ans.pb(y);
	ans.pb(x);
}
void Encrypt()
{
	int mn=0;
    for(int i=0;i<groups.size();i++) if(i==0 || groups[mn].first>groups[i].first) mn=i;
    int key=*groups[mn].second.begin();
    for(int i=seq.size()-1;i>=0;i--)
	{
		//printf("\ni:%i key:%i",i,key);
		if(change[key].count(i))
		{
			int nKey=change[key][i];
			ChangeKey(nKey,key);
			key=nKey;
		}
		Add(key,seq[i].first,seq[i].second);
	}
	if(key!=0) ChangeKey(0,key);
	reverse(ans.begin(),ans.end());
}
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++) scanf("%i",&a[i]);
	Decrypt();
	Solve();
	Encrypt();
	printf("%i\n",ans.size());
	for(int i:ans) printf("%i ",i);
	printf("\n");
	return 0;
}

Compilation message (stderr)

rle.cpp: In function 'void Check()':
rle.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<groups.size();i++)
              ~^~~~~~~~~~~~~~
rle.cpp: In function 'void Solve()':
rle.cpp:77:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int tm=0;tm<seq.size();tm++)
               ~~^~~~~~~~~~~
rle.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<groups.size();i++)
               ~^~~~~~~~~~~~~~
rle.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=i+1;j<groups.size();j++)groups[j-1]=groups[j];
                    ~^~~~~~~~~~~~~~
rle.cpp:99:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<groups.size();i++)
               ~^~~~~~~~~~~~~~
rle.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<groups.size();i++) if(groups[i].first==dp)
               ~^~~~~~~~~~~~~~
rle.cpp: In function 'void Encrypt()':
rle.cpp:158:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<groups.size();i++) if(i==0 || groups[mn].first>groups[i].first) mn=i;
                 ~^~~~~~~~~~~~~~
rle.cpp: In function 'int main()':
rle.cpp:181:26: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%i\n",ans.size());
                ~~~~~~~~~~^
rle.cpp:176:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
rle.cpp:177:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i",&a[i]);
                        ~~~~~^~~~~~~~~~~~
rle.cpp: In function 'void Solve()':
rle.cpp:82:7: warning: 'dp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int dp;
       ^~

• Subtask 1: 90 / 100