This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
char res[600002];
int area[600002];
bool solve(int ll, int rr, vector<int>& A, vector<int>& other) {
if (ll > rr) return true;
res[ll] = '^';
res[other[ll]] = '^';
while (1) {
area[ll] = 0;
for (int i=ll+1; i<=rr; i++)
area[i] = area[i-1] + (res[i] == '^' || res[i] == 'v');
int ok = 0;
for (int i=ll+1; i<=other[ll]-1; i++)
if (res[i] != '^' && res[i] != 'v' && area[i] != area[other[i]]) {
int lll = i;
int rrr = other[i];
if (lll > rrr) swap(lll, rrr);
int p1 = 0, p2 = 0;
for (int j=lll+1; j<=rrr-1; j++)
if (res[j] == '^' && (other[j] < lll || other[j] > rrr)) p1 = 1;
else if (res[j] == 'v' && (other[j] < lll || other[j] > rrr)) p2 = 1;
if (p1 && p2) return false;
if (p1) res[lll] = res[rrr] = 'v';
else res[lll] = res[rrr] = '^';
ok = 1;
break;
}
if (!ok) break;
}
int st = ll+1;
for (int i=ll+1; i<=rr; i++)
if (res[i] == '^' || res[i] == 'v') {
bool ret = solve(st, i-1, A, other);
if (!ret) return false;
st = i+1;
}
return solve(st, rr, A, other);
}
int main()
{
int n;
cin >> n;
vector<int> A(2*n);
vector<pair<int, int> > P;
for (int i=0; i<2*n; i++) {
cin >> A[i];
A[i] --;
P.push_back(pair<int, int>(A[i], i));
}
sort(P.begin(), P.end());
vector<int> other(2*n);
for (int i=0; i<2*n; i+=2) {
int a = P[i].second;
int b = P[i+1].second;
other[a] = b;
other[b] = a;
}
for (int i=0; i<2*n; i++) res[i] = '_';
res[2*n] = 0;
bool ret = solve(0, 2*n-1, A, other);
if (ret) cout << res << endl;
else cout << "IMPOSSIBLE" << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |