oj.uz

Submission #580594

# Submission time Handle Problem Language Result Execution time Memory
580594 2022-06-21T13:19:57 Z AGE Drvca (COCI19_drvca) C++14
30 / 110
 215 ms 23456 KB 
#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,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 ok=0;

    set<int>sttt;

    for(int i=0;i<n;i++)
        sttt.insert(a[i]);

    if(sttt.size()==1){

        cout<<n/2<<endl;
        for(int i=0;i<n/2;i++)
            cout<<*sttt.begin()<<" ";

        cout<<endl;
        cout<<(n+1)/2<<endl;
        for(int i=0;i<(n+1)/2;i++)
            cout<<*sttt.begin()<<" ";

        cout<<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.begin()==*st.rbegin())
                Final_ans=num,ans.F=ii,ans.S=jj;

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

                //cout<<i<<"!"<<endl;
                if(Final_ans)
                    break;

                num++;

                if(st.size()==1)
                    break;

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

                int x=i;

                auto itt=--st.end();
                auto itt2=st.find(i);

                if(itt2==itt){

                    //cout<<"@#"<<endl;
                    auto it=--st.find(i);
                    int diff2=(abs(*it-x));

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

                    stt.erase(stt.find(diff2));

                }

                else if(st.find(i)==st.begin()){
                    auto ittt=++st.find(i);

                    int diff2=abs((*ittt)-x);

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

                    stt.erase(stt.find(diff2));
                  //  cout<<diff2<<endl;

                    //cout<<"!@!"<<endl;
                }

                else{
                    //cout<<"FI"<<endl;
                    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));
                    if(stt.size())
                        stt.erase(stt.find(diff1));

                    if(stt.size())
                        stt.erase(stt.find(diff2));

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

                }

                if(*stt.begin()==*stt.rbegin())
                    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]);

    for(int i=0;i<n;i++)
        mp[a[i]]++;
    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]]--;


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

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

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

        v2.pb(a[i]);
        mp[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

drvca.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main()
      | ^~~~
drvca.cpp: In function 'int main()':
drvca.cpp:229: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]
  229 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
drvca.cpp:234: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]
  234 |     for(int i=0;i<v2.size();i++)
      |                 ~^~~~~~~~~~
drvca.cpp:46:9: warning: unused variable 'ok' [-Wunused-variable]
   46 |     int ok=0;
      |         ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 23368 KB Output is correct
2 Correct 190 ms 18584 KB Output is correct
3 Correct 209 ms 23244 KB Output is correct
4 Correct 160 ms 18584 KB Output is correct
5 Correct 215 ms 23332 KB Output is correct
6 Correct 160 ms 18572 KB Output is correct
7 Correct 205 ms 23456 KB Output is correct
8 Correct 180 ms 18596 KB Output is correct
9 Correct 159 ms 18136 KB Output is correct
10 Correct 176 ms 19128 KB Output is correct
11 Correct 72 ms 2024 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -