oj.uz

답안 #76844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76844 2018-09-18T15:37:44 Z zetapi Gift (IZhO18_nicegift) C++14
0 / 100
 2000 ms 103856 KB 
#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=1e6;

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));
	for(int A=0;A<res.size();A++)
		cout<<1<<" "<<res[A].first<<" "<<res[A].second<<"\n";
	while(!st.empty())
	{
		it_1=st.begin();
		it_2=it_1;
		it_2++;
		cout<<1<<" "<<it_1->second<<" "<<it_2->second<<"\n";
		st.erase(it_1);
		st.erase(it_2);
	}
	return ;
}

void print_3()
{
	vector<pii> vec;
	while(!st.empty())
	{
		it_1=st.begin();
		vec.pb(mp(-1*it_1->first,it_1->second));
		st.erase(it_1);
	}
	assert(vec.size()==3);
	sort(vec.begin(),vec.end());
	if((vec[0].first+vec[1].first<vec[2].first) or ((vec[0].first+vec[1].first)%2!=vec[2].first%2))
	{
		cout<<-1<<"\n";
		exit(0);
	}
	else
	{
		for(int A=0;A<res.size();A++)
			cout<<1<<" "<<res[A].first<<" "<<res[A].second<<"\n"; 
		while((vec[0].first+vec[1].first)!=vec[2].first)
		{
			cout<<1<<" "<<vec[0].second<<" "<<vec[1].second<<" "<<"\n";
			vec[0].first--;
			vec[1].first--;
		}
		assert(vec[0].first+vec[1].first==vec[2].first);
		if(vec[0].first)
			cout<<vec[0].first<<" "<<vec[0].second<<" "<<vec[2].second<<"\n";
		if(vec[1].first)
			cout<<vec[1].first<<" "<<vec[1].second<<" "<<vec[2].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(st.size()==2)
		{
			if(it_1->first==it_2->first)
				cout<<-1*it_1->first<<" "<<it_1->second<<" "<<it_2->second<<"\n";
			else
				cout<<-1<<"\n";
			exit(0);
		}
		if(st.size()==3)
		{
			print_3();
			break;
		}
		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));
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Not all heaps are empty in the end
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Not all heaps are empty in the end
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Not all heaps are empty in the end
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 103856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Not all heaps are empty in the end
2 Halted 0 ms 0 KB -