Submission #77110

#	Time	Username	Problem	Language	Result	Execution time	Memory
77110		zetapi	Gift (IZhO18_nicegift)	C++14	100 / 100	1470 ms	254116 KiB

nicegift

#include "bits/stdc++.h"
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define int long long
#define itr iterator

typedef pair<ll,ll> pii;

const ll MAX=2e6;
const ll INF=1e12;

vector<pii> vec;

vector<pair<ll,set<ll>>> res;

ll N,K,sum,mx,arr[MAX];

void insert(int X,int Y,int Z)
{
	vec.pb(mp(X,Z));
	vec.pb(mp(Y+1,-Z));
}

signed main()
{
	ios_base::sync_with_stdio(false);

	cin>>N>>K;
	for(int A=1;A<=N;A++)
	{
		cin>>arr[A];
		sum+=arr[A];
		mx=max(mx,arr[A]);
	}
	if(sum%K or mx>sum/K)
		return cout<<-1,0;
	int lst=1,row=K,col=sum/K;
	for(int A=1;A<=N;A++)
	{
		if(lst+arr[A]-1>col)
			insert(lst,col,A),
			insert(1,arr[A]-(col-lst+1),A);
		else
			insert(lst,lst+arr[A]-1,A);
		lst=(lst-1+arr[A])%col+1;
	}
	sort(vec.begin(),vec.end());
	int ptr=0;
	set<int> st;
	while(ptr<vec.size())
	{
		int cur=ptr;
		while(ptr<vec.size() and vec[cur].first==vec[ptr].first)
		{
			if(vec[ptr].second<0)
				st.erase(-vec[ptr].second);
			else
				st.insert(vec[ptr].second);
			++ptr;
		}
		if(ptr<vec.size())
			res.pb(mp(vec[ptr].first-vec[cur].first,st));
	}
	cout<<res.size()<<"\n";
	for(auto A:res)
	{
		cout<<A.first<<" ";
		for(auto B:A.second)
			cout<<B<<" ";
		cout<<"\n";
	}
	return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr<vec.size())
        ~~~^~~~~~~~~~~
nicegift.cpp:56:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<vec.size() and vec[cur].first==vec[ptr].first)
         ~~~^~~~~~~~~~~
nicegift.cpp:64:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr<vec.size())
      ~~~^~~~~~~~~~~
nicegift.cpp:40:12: warning: unused variable 'row' [-Wunused-variable]
  int lst=1,row=K,col=sum/K;
            ^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51