# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
76833 | zetapi | Gift (IZhO18_nicegift) | C++14 | 2054 ms | 117612 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,arr[MAX];
void print_1()
{
assert(!(st.size()%2));
for(int A=0;A<res.size();A++)
cout<<res[A].first<<" "<<res[A].second<<" "<<1<<"\n";
while(!st.empty())
{
it_1=st.begin();
it_2=it_1;
it_2++;
cout<<it_1->second<<" "<<it_2->second<<" "<<1<<"\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);
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<<res[A].first<<" "<<res[A].second<<" "<<1<<"\n";
while((vec[0].first+vec[1].first)!=vec[2].first)
{
cout<<vec[0].second<<" "<<vec[1].second<<" "<<1<<"\n";
vec[0].first--;
vec[1].first--;
}
assert(vec[0].first+vec[1].first==vec[2].first);
if(vec[0].first)
cout<<vec[0].second<<" "<<vec[2].second<<" "<<vec[0].first<<"\n";
if(vec[1].first)
cout<<vec[1].second<<" "<<vec[2].second<<" "<<vec[1].first<<"\n";
}
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin>>N>>K;
for(int A=1;A<=N;A++)
{
cin>>arr[A];
st.insert(mp(-arr[A],A));
}
while(true)
{
if(st.size()==3)
{
print_3();
break;
}
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);
st.insert(p);
st.insert(q);
res.pb(mp(p.second,q.second));
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |