Submission #306901

#	Time	Username	Problem	Language	Result	Execution time	Memory
306901		dolijan	Drvca (COCI19_drvca)	C++14	110 / 110	298 ms	12408 KiB

drvca

#include<bits/stdc++.h>
using namespace std;
const int mn=1e5+100;
int a[mn];
bool check(int prvi,int drugi,int n)
{
    vector<int> aa;
    vector<int> bb;
    multiset<int> preostali;
    multiset<int> razlike;
    multiset<int>::iterator it,ptr;
    aa.push_back(a[prvi]);
    aa.push_back(a[drugi]);
    for(int i=0;i<drugi;i++)
    {
        if(i!=prvi) preostali.insert(a[i]);
    }
    for(int i=drugi+1;i<n;i++)
    {
        preostali.insert(a[i]);
    }
    it=preostali.begin();
    ptr=it;
    it++;
    while(it!=preostali.end())
    {
        razlike.insert(*it-*ptr);
        it++; ptr++;
    }
    int raz=a[drugi]-a[prvi];
    for(int i=drugi+1;i<n;i++)
    {
        int zad=aa[aa.size()-1];
        if(a[i]-zad==raz)
        {
            aa.push_back(a[i]);
            it=preostali.find(a[i]);
            multiset<int>::iterator kraj=preostali.end();
            kraj--;
            if(it==preostali.begin())
            {
                ptr=it;
                ptr++;
                preostali.erase(preostali.find(*it));
                razlike.erase(razlike.find(*ptr-*it));
            }
            else if(it==kraj)
            {
                ptr=it;
                ptr--;
                preostali.erase(preostali.find(*it));
                razlike.erase(razlike.erase(*it-*ptr));
            }
            else
            {
                ptr=it;
                multiset<int>::iterator veci=it;
                veci++;
                ptr--;
                preostali.erase(preostali.find(*it));
                razlike.erase(razlike.find(*it-*ptr));
                razlike.erase(razlike.find(*veci-*it));
                razlike.insert(*veci-*ptr);
            }
        }
        if(!razlike.empty())
        {
            it=razlike.begin();
            ptr=razlike.end();
            ptr--;
            if(*it==*ptr)
            {
                /*it=razlike.begin();
                while(it!=razlike.end())
                {
                    cout<<*it<<" ";
                    it++;
                }*/
                //cout<<endl;
                break;
            }
        }
    }
    if(!razlike.empty())
    {
        it=razlike.begin();
        ptr=razlike.end();
        ptr--;
        if(*it!=*ptr) return false;
    }
    if((int)preostali.size()==0)
    {
        preostali.insert(aa[aa.size()-1]);
        aa.pop_back();
    }
    cout<<aa.size()<<endl;
    for(int i=0;i<aa.size();i++) cout<<aa[i]<<" ";
    cout<<endl;
    cout<<preostali.size()<<endl;
    it=preostali.begin();
    while(it!=preostali.end())
    {
        cout<<*it<<" ";
        it++;
    }
    cout<<endl;
    return true;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    /*for(int i=0;i<n;i++) cout<<a[i]<<" ";
    cout<<endl;*/
    if(n==2)
    {
        cout<<1<<endl;
        cout<<a[0]<<endl;
        cout<<1<<endl;
        cout<<a[1]<<endl;
    }
    else
    {
        if(!check(0,1,n))
        {
            if(!check(0,2,n))
            {
                if(!check(1,2,n))
                {
                    cout<<-1<<endl;
                }
            }
        }
    }
}

Compilation message (stderr)

drvca.cpp: In function 'bool check(int, int, int)':
drvca.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<aa.size();i++) cout<<aa[i]<<" ";
      |                 ~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30