답안 #243640

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243640 2020-07-01T13:01:55 Z TadijaSebez RLE (BOI06_rle) C++11
90 / 100
2500 ms 117132 KB
#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

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;
       ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5760 KB Output is correct
2 Correct 9 ms 5760 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 11 ms 5888 KB Output is correct
5 Correct 9 ms 5888 KB Output is correct
6 Correct 38 ms 7920 KB Output is correct
7 Correct 228 ms 19484 KB Output is correct
8 Correct 304 ms 23940 KB Output is correct
9 Correct 645 ms 51516 KB Output is correct
10 Correct 230 ms 18908 KB Output is correct
11 Correct 181 ms 16876 KB Output is correct
12 Correct 735 ms 49616 KB Output is correct
13 Correct 508 ms 36764 KB Output is correct
14 Correct 264 ms 24412 KB Output is correct
15 Correct 151 ms 15972 KB Output is correct
16 Correct 493 ms 39516 KB Output is correct
17 Correct 724 ms 45756 KB Output is correct
18 Correct 1002 ms 60480 KB Output is correct
19 Execution timed out 2598 ms 81816 KB Time limit exceeded
20 Execution timed out 2575 ms 117132 KB Time limit exceeded