PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array A that contains every integer from 1 to N exactly twice.
Find a permutation P of \{1, 2, \ldots, N\} such that:
- For each i = 1, 2, \ldots, N, delete both instances of P_j for j \gt i.
In the resulting array, the two occurrences of P_i should have at most \frac{|A|}{2} elements between them.
EXPLANATION:
Observe that when checking the condition for i, we’re essentially taking the subsequence of A that contains only the elements \{P_1, P_2, \ldots, P_i\}; everything else is deleted.
Each such element occurs exactly twice in A, so this subsequence has length 2i — and our aim is to ensure that in this subsequence, both occurrences of P_i have at most \frac{2i}{2} = i elements between them.
Since there are i-1 distinct elements (other than P_i), one way to achieve this is to ensure that each P_j (for j\lt i) occurs at most once between the occurrences of P_i.
One relatively easy way to attain this is as follows:
- Let L_i denote the index of the leftmost occurrence of i in A.
This is easily computed in \mathcal{O}(N) time. - Then, create P in increasing order of L_i values.
That is, P_i will be the element with the i-th smallest L-value.
For example, if A = [1, 2, 1, 4, 2, 3, 3, 4], we’ll have L = [1, 2, 6, 4].
This gives us the answer permutation P = [1, 2, 4, 3].
It’s not hard to see that this always works: after all, when looking at P_i, we know that for every j \lt i L_{P_j} \lt L_{P_i} will hold (by construction).
This means each P_j occurs at least once before the leftmost occurrence of P_i, meaning each P_j can also occur at most once between the two occurrences of P_i — exactly what we wanted!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll int
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;
const ll MAX=500500;
void solve(){
ll n; cin>>n;
vector<ll> ans,found(n+5,0);
for(ll i=1;i<=2*n;i++){
ll x; cin>>x;
if(!found[x]){
ans.push_back(x);
}
found[x]=1;
}
for(ll i=0;i<n;i++){
cout<<ans[i]<<" \n"[i+1==n];
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#define IGNORE_CR
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 3e5);
sn += n;
in.readEoln();
auto a = in.readInts(2 * n, 1, n);
in.readEoln();
{
vector<int> b(n);
for (int i : a) {
b[i - 1]++;
}
for (int i = 0; i < n; i++) {
assert(b[i] == 2);
}
}
vector<int> c(n, -1);
for (int i = 0; i < 2 * n; i++) {
if (c[a[i] - 1] == -1) {
c[a[i] - 1] = i;
}
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return c[i] < c[j];
});
for (int i = 0; i < n; i++) {
cout << order[i] + 1 << " ";
}
cout << '\n';
}
in.readEof();
assert(sn <= 3e5);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
lt = [2*n+1]*(n+1)
for i in range(2*n):
x = a[i]
lt[x] = min(lt[x], i)
ind = list(range(1, n+1))
ind.sort(key= lambda x: lt[x])
print(*ind)