ProveMeRight's blog

By ProveMeRight, history, 20 months ago, In English

196344788

Please check for this.

/*
                    ------ Ackerman ------
     A single soldier might pose a threat to me?
     Yes! Captain Levi is Dangerous.   
*/

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define FOR(i,a,b)     for (int i = a; i < b; i++)

//---------- MOD Operations (Unleash the Beast Mode) -----------------------


int mod = 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % mod);
}

inline int powerM(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  a %= mod;
  if (a < 0) a += mod;
  int b = mod, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += mod;
  return u;
}

//-------------------------------------------------------------


inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}


// O(logN) -> __gcd(a,b);


// int gcd(int a,int b)
// {
//   if(b==0) return a;
//   return gcd(b,a%b);
// }


// negative mod
inline int Nmode(int x,int m)
{
   x = x%m;
    if (x < 0) x += m;
    return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

// const int N = 200005;

/* void sieve()
{
  is_prime[0]=is_prime[1] = true;
  for(int i=2;i<=N;i++)
  {
    if(is_prime[i]==false && i*i<=N)
    {
      for(int j = i*i;j<=N;j+=i)
      {
        is_prime[j]= true;
      }
    }
  }
}
*/

void solve() {
    int n;
    cin >> n;
    vi v(n);
    FOR(i,0,n) cin >> v[i];

    if(n==1)
    {
        cout << "YES" << endl;
        cout << 1 << endl;
        cout << 1 << endl;
        return;
    }

    set<int>s1,s2;

    FOR(i,1,n+1)
    {
        s1.insert(i);
        s2.insert(i);
    }

    vector<int>p(n,0),q(n,0);
    FOR(i,0,n)
    {
        int val = v[i];

        if(s1.find(val)!=s1.end())
        {
            p[i] = val;
            s1.erase(s1.find(val));
        }
        else if(s2.find(val)!=s2.end())
        {
            q[i] = val;
            s2.erase(s2.find(val));
        }
        else
        {
            cout << "NO" << endl;
            return;
        }
    }


    FOR(i,0,n)
    {
        if(p[i]==0)
        {
            auto it = upper_bound(s1.begin(),s1.end(),q[i]);
            if(it==s1.begin())
            {
                cout << "NO" << endl;
                return;
            }
            it--;

            p[i] = *it;
            s1.erase(it);
        }
    }

    FOR(i,0,n)
    {
        if(q[i]==0)
        {
            auto it = upper_bound(s2.begin(),s2.end(),p[i]);
            if(it==s2.begin())
            {
                cout << "NO" << endl;
                return;
            }
            it--;

            q[i] = *it;
            s2.erase(it);
        }
    }

    cout << "YES" << endl;
    print(p);
    print(q);
}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// #ifndef ONLINE_JUDGE
//   freopen("input.txt",  "r",  stdin);
//   freopen("output.txt", "w", stdout);
// #endif

  clock_t z = clock();

  int t = 1;
  cin >> t;
  while (t--) solve();

  cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

  return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Set/Map/Multiset has it's own lower_bound/upper_bound function. So prefer using s1.upper_bound(val).

For more refer this

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Just a suggestion, if your code is too big you should simply share its submission link instead of complete code.