Codeforces Round 671 Div 2 Problem D2

help
1 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast")
// #pragma GCC optimize "trapv"
#define lld long long int 

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    //cin>>t;
    t=1;
    while(t--)
    {
        int n;
        cin>>n;
        int arr[n];
        int res[n];
        map <int, int> mp;
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            mp[arr[i]]++;
        }
        if(mp.size()==1)
        {
            for(int i=0;i<n;i++)
            res[i]=arr[i];
        }
        
        else{
        
        auto it=--mp.end();
        auto previt=it;
        previt--;
        res[0]=it->first;
        mp[it->first]--;
        int k=0;
        
        //cout<<previt->first<<"\n";
        if(previt==mp.begin() && mp[it->first]==0)  //when count of second smallest number comp 
        {
            for(k=k+1;k<n;k++)
            res[k]=previt->first;
            break;
        }
        if(previt==mp.begin() && mp[previt->first]==0) //when count of smallest number comp
        {
            for(k=k+1;k<n;k++)
            res[k]=it->first;
            break;
        }
            
        if(mp[it->first]==0)
        {
            it=previt;
            previt--;
        }
        
        for(k=1;k<n;k++)
        {
            if(previt==mp.begin() && mp[it->first]==0)
            {
                for(k=k;k<n;k++)
                res[k]=previt->first;
                break;
            }
            if(previt==mp.begin() && mp[previt->first]==0)
            {
                for(k=k;k<n;k++)
                res[k]=it->first;
                break;
            }
            
            if(mp[previt->first]==0)
            previt--;
            
            if(mp[it->first]==0)
            {
                it=previt;
                previt--;
            }
            
            res[k]=previt->first;
            k++;
            if(k==n)
            break;
            res[k]=it->first;
            mp[it->first]--;
            mp[previt->first]--;
            
        }}
        int cnt=0;
        for(int i=1;i<n-1;i++)
        if(res[i]<res[i-1] && res[i]<res[i+1])
        cnt++;
        
        cout<<cnt<<"\n";
        for(int i=0;i<n;i++)
        cout<<res[i]<<" ";
    }
}

I am getting WA on TC 7. Can someone provide small TC for which this code will fail?

@akshitm16 @everule1 @ssjgz

2

Test case :

9
1 1 1 1 3 4 6 8 9 
your output:
3
9 6 8 3 4 6 1 6 1 
correct output:
4
3 1 4 1 6 1 8 1 9

hopefully you will get it after this where you are going wrong!! :slight_smile:

2 Likes