Submission #580424

#	Time	Username	Problem	Language	Result	Execution time	Memory
580424		AGE	Drvca (COCI19_drvca)	C++14	0 / 110	72 ms	11776 KiB

drvca

#include<bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back

using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;

multiset<int>st;
set<int>stt;
pair<int,int>ans;
vector<int>v,v2;
map<int,int>mp;

int a[N];
main()
{

    int n;
    cin>>n;

    for(int i=0;i<n;i++)
        cin>>a[i];

    sort(a,a+n);

    if(n==2){

        cout<<1<<endl;
        cout<<a[0]<<endl;
        cout<<1<<endl;
        cout<<a[1]<<endl;
        return 0;

    }

    if(n==3){
        cout<<2<<endl;
        cout<<a[0]<<" "<<a[1]<<endl;
        cout<<1<<endl;
        cout<<a[2]<<endl;
        return 0;
    }
    int Final_ans=0;
    for(int ii=0;ii<=2;ii++){

        if(Final_ans!=0)
            break;

        for(int jj=ii+1;jj<=2;jj++){

            if(Final_ans!=0)
                break;

            st.clear(),stt.clear();

            int x=a[ii];
            int y=a[jj];

            int diff=y-x;
            int lst=y;

            for(int i=n-1;i>=0;i--)
                if(i!=ii&&i!=jj)
                    lst=i;

            for(int i=0;i<n;i++){

                if(i==ii||i==jj)
                    continue;

                st.insert(a[i]);

                if(i==lst)
                    continue;

                stt.insert(a[i]-a[lst]);
                lst=i;

            }


            /*for(auto x:st)
                cout<<x<<" ";
            cout<<endl;

            for(auto x:stt)
                cout<<x<<" ";
            cout<<endl;

            cout<<endl;*/

            int lst2=y,num=2;

            if(stt.size()==1)
                Final_ans=num,ans.F=ii,ans.S=jj;

            for(int i=lst2+diff;i>=1;i+=diff){

                if(Final_ans)
                    break;

                num++;

                if(st.find(i)==st.end())
                    break;

                int x=i;

                if((*st.find(i))==(*st.rbegin())){

                    auto it=--st.find(i);
                    int diff=(abs(*it-x));

                    st.erase(st.find(i));

                    stt.erase(stt.find(diff));

                }

                else if(st.find(i)==st.begin()){

                    auto it=++st.find(i);
                    int diff=abs(*it-x);

                    st.erase(st.find(i));

                    stt.erase(stt.find(diff));

                }

                else{

                    auto it=++st.find(i);
                    auto it2=--st.find(i);
                    int diff1=abs(*it-x);
                    int diff2=abs(*it2-x);

                    st.erase(st.find(i));
                    stt.erase(stt.find(diff1));
                    stt.erase(stt.find(diff2));

                    stt.insert(abs(*it-*it2));

                }

                if(stt.size()==1)
                    Final_ans=num,ans.F=ii,ans.S=jj;
            }

        }
    }

    //cout<<Final_ans<<" "<<ans.F<<" "<<ans.S<<endl;

    if(Final_ans==0){

        cout<<"-1"<<endl;
        return 0;

    }

    v.pb(a[ans.F]);
    v.pb(a[ans.S]);

    int diff=a[ans.S]-a[ans.F];

    for(int i=0;i<Final_ans-2;i++)
        v.pb(v[v.size()-1]+diff),mp[v[v.size()-1]]=1;


    for(int i=0;i<n;i++){

        if(i==ans.F||i==ans.S)
            continue;

        if(mp[a[i]])
            continue;

        v2.pb(a[i]);

    }

    cout<<v.size()<<endl;

    for(int i=0;i<v.size();i++)
        cout<<v[i]<<" ";
    cout<<endl;

    cout<<v2.size()<<endl;
    for(int i=0;i<v2.size();i++)
        cout<<v2[i]<<" ";
    cout<<endl;

    return 0;
}

Compilation message (stderr)

drvca.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main()
      | ^~~~
drvca.cpp: In function 'int main()':
drvca.cpp:187:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
drvca.cpp:192:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     for(int i=0;i<v2.size();i++)
      |                 ~^~~~~~~~~~

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