Polygonal Chain

input/code.cpp: In function 'int main()':
input/code.cpp:87:14: warning: unused variable 'd' [-Wunused-variable]
     ll a,b,c,d;
              ^

#pragma GCC optimize("O3")   //
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;

unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);

ll random2(){
    return (1ll << 31ll)*eng()+eng();
}

ll n,m,k,q,T;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const int MAXN = 200002;

string dirs;
vl X;

vl Y;

bool bad(int i, int j){
    if(i == n)return 0;
    if(j == 0)return 0;
    ll mi = min(X[i+1], X[i]);
    ll ma = max(X[i+1], X[i]);
    if(X[j] < mi || X[j] > ma)return 0;
    return 1;
}

bool bad2(int i, int j){
    if(!bad(i, j))return 0;
    if(i == j-1 || i == j)return 0;
    if(Y[i] < min(Y[j-1], Y[j]))return 0;
    if(Y[i] > max(Y[j-1], Y[j]))return 0;
    return 1;
}

bool valid(){
    rep(c1,0,n-1){
        if(dirs[c1] == 'U'){
            if(Y[c1] >= Y[c1+1])return 0;
        }
        else{
            if(Y[c1] <= Y[c1+1])return 0;
        }
    }
    return 1;
}

int bads(){
    int res = 0;
    rep(c1,0,n){
        rep(c2,0,n){
            if(c1 != c2){
                res += bad2(c1,c2);
            }
        }
    }
    if(!valid())return 12543543;
    return res;
}

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

    //freopen("fhc.txt","r",stdin);
    //freopen("autput.txt","w",stdout);

    ll a,b,c,d;

    cin >> n;
    X.push_back(0);
    rep(c1,0,n){
        cin >> a;
        if(c1%2 == 1)a = -a;
        X.push_back(X[c1]+a);

    }
    cin >> dirs;

    rep(c1,0,n){
        Y.push_back(c1);
    }

    ll L = 0;
    ll R = n-1;

    for(int c1 = n-1; c1 >= 0; c1--){
        if(c1 == 0){
            Y[c1] = R;
            break;
        }
        if(dirs[c1-1] == 'U'){
            Y[c1] = R;
            R--;
        }
        else{
            Y[c1] = L;
            L++;
        }
    }

    int lim = 10000000/(n*n);
    b = -1;
    for(int c4 = 0; c4 < lim; c4++){

        if(c4%100 == 0){
            random_shuffle(all(Y));
            b = -1;
        }

        if(b == -1)b = bads();
        if(b == 0)break;
        int l,r;



        rep(c1,0,100){
            l = random2()%n;
            r = random2()%n;
            if(l == r)continue;
            swap(Y[l], Y[r]);
            if(!valid()){
                swap(Y[l], Y[r]);
                continue;
            }
            break;
        }
        c = bads();
        if(c >= b){
            swap(Y[l], Y[r]);
        }
        else{
            b = -1;
        }

    }

    if(bads() == 0){
        cout << "YES\n";
        rep(c1,0,n-1){
            cout << abs(Y[c1+1]-Y[c1]) << " ";
        }cout << "\n";
    }
    else{
        cout << "NO\n";
    }

    return 0;
}

Test 1

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 9

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 2, 4, 5

Verdict: ACCEPTED

Test 11

Group: 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 3, 4, 5

Verdict: ACCEPTED

Test 15

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 16

Group: 4, 5

Verdict: WRONG ANSWER

Test 17

Group: 4, 5

Verdict: WRONG ANSWER

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 20

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 21

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 22

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 23

Group: 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 4, 5

Verdict: WRONG ANSWER

Test 25

Group: 4, 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2, 4, 5

Verdict: ACCEPTED