In problem C, I wrote a solution that showed me the wrong answer on test case
For Those who don't know what is problem C 38
6 9 6 6 6 2 8 6 6 8 5 4 6 6 9 0 0 4 4 3 6 0 0 5 4 5 0 8 4 6 4 8 0 7 5 0 0 8
My first code output 196
, AC code output 210
My first code lexicographically largest array
9 8 7 6 9 8 6 8 6 5 4 3 2 0 8 6 5 4 0 8 6 5 4 0 6 5 4 0 6 4 0 6 4 0 6 0 6 0
AC code lexicographically largest array
9 8 7 6 5 4 3 2 0 9 8 6 5 4 0 8 6 5 4 0 8 6 5 4 0 8 6 4 0 6 6 6 4 0 6 0 6 0
I was amazed as I was sure with my logic, but after (successfully wasting more than 1.5 hours) I changed my approach and it got AC. After the contest was over I was thinking why my first solution was wrong and stress tested it. I got a test case
4
2 1 2 3
My first code is giving the lexicographically largest array as 3 2 2 1
whereas my AC code is giving 3 2 1 2
, I am completely confused as the first output is better than the second one. Please help!
I am attaching my first code here.
Code#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//User function Template for C++
int solve(vector<int> &A) {
int n = A.size();
vector<int> ar(n);
vector<int> fre(10);
for (int i = 0; i < n; i++)
fre[A[i]]++;
int ass = *max_element(fre.begin(), fre.end());
int gro = 1;
vector<bool> cur(10);
for (int i = 0; i < n; i++) {
for (int j = 9; j >= 0; j--) {
if (fre[j] > 0) {
int abhi = gro;
vector<bool> pref = cur;
vector<int> suf = fre;
if (cur[j] == 0)
pref[j] = 1;
else {
pref.assign(10, 0);
pref[j] = 1;
abhi++;
}
suf[j]--;
for (int k = 0; k < 10; k++)
if (pref[k] == 0 && suf[k] > 0)
suf[k]--;
int num = *max_element(suf.begin(), suf.end());
if (num + abhi == ass) {
fre[j]--;
ar[i] = j;
cur = pref;
gro = abhi;
break;
}
}
}
}
{
// prints the lexicographicall largest array
for (int i = 0; i < n; i++) {
cout << ar[i] << " ";
}
cout << "\n";
}
vector<int> v[10];
for (int i = n - 1; i >= 0; i--) {
v[A[i]].push_back(i);
}
vector<int> arr(n);
oset os;
for (int i = 0; i < n; i++) {
arr[v[ar[i]].back()] = i + 1;
v[ar[i]].pop_back();
os.insert(i + 1);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
os.erase(arr[i]);
ans += os.order_of_key(arr[i]);
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
vector<int> A(n);
for (int i = 0; i < n; i++)
cin >> A[i];
cout << solve(A) << endl;
return 0;
}
Sorry for my bad English.
Full text and comments »