Submission #76849

#	Time	Username	Problem	Language	Result	Execution time	Memory
76849		zetapi	Gift (IZhO18_nicegift)	C++14	18 / 100	2059 ms	104688 KiB

nicegift

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

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

typedef pair<int,int> pii;

const int MAX=5e6;

set<pii> st;

set<pii>::itr it_1,it_2;

vector<pii> res;

int N,K,sum,arr[MAX];

void print_1()
{
	assert(!(st.size()%2));
	while(!st.empty())
	{
		it_1=st.begin();
		it_2=it_1;
		it_2++;
		res.pb(mp(it_1->second,it_2->second));
		st.erase(it_1);
		st.erase(it_2);
	}
	cout<<res.size()<<"\n";
	for(int A=0;A<res.size();A++)
		cout<<1<<" "<<res[A].first<<" "<<res[A].second<<"\n";
	return ;
}

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

	cin>>N>>K;
	for(int A=1;A<=N;A++)
	{
		cin>>arr[A];
		sum+=arr[A];
		if(arr[A])
			st.insert(mp(-arr[A],A));
	}
	if(sum%2)
		return cout<<-1,0;
	while(true)
	{
		if(st.size()<=1)
			return cout<<-1,0;
		it_1=st.begin();
		it_2=it_1;
		it_2++;
		pii p=*it_1;
		pii q=*it_2;
		if(p.first==-1)
		{
			print_1();
			break;
		}
		p.first++;
		q.first++;
		st.erase(it_1);
		st.erase(it_2);
		if(p.first!=0)
			st.insert(p);
		if(q.first!=0)
			st.insert(q);
		res.pb(mp(p.second,q.second));
		/*for(auto A:st)
			cout<<-A.first<<" ";
		cout<<"\n";*/
	}
	return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'void print_1()':
nicegift.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<res.size();A++)
              ~^~~~~~~~~~~

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