Polygonal Chain

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
const int MAX_N = 1e5;
int length_ver[1 + MAX_N], length_hor[1 + MAX_N];


struct Segment {
    pair <int, int> a;
    pair <int, int> b;
};

#define Point pair <int, int>
#define x first
#define y second
bool onSegment(Point p, Point q, Point r)  {
    if (q.x < max(p.x, r.x) && q.x > min(p.x, r.x) &&
        q.y < max(p.y, r.y) && q.y > min(p.y, r.y))
       return true;

    return false;
}
int orientation(Point p, Point q, Point r)
{
    ll val = 1ll * (q.y - p.y) * (r.x - q.x) -
              1ll * (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;

    return (val > 0)? 1: 2;
}

bool doIntersect (Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4)
        return true;
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
    return false;
}


int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> length_ver[i];
    string direction;
    cin >> direction;
    direction = " " + direction;
    for (int i = 1; i < n; i++)
        length_hor[i] = (1 << (30 - i));
    vector <pair <int, int>> points;
    points.pb ({0, 0});
    pair <int, int> cur_point = {0, 0};
    for (int i = 1; i <= n; i++) {
        int ori;
        if (i % 2)
            ori = 1;
        else
            ori = -1;
        cur_point.second += ori * length_ver[i];
        points.pb (cur_point);
        if (i < n) {
            if (direction[i] == 'U')
                ori = 1;
            else
                ori = -1;
            cur_point.first += ori * length_hor[i];
            points.pb (cur_point);
        }
    }
    int sz = points.size ();
    vector <Segment> segments;
    for (int i = 0; i + 1 < sz; i++)
        segments.pb ({points[i], points[i + 1]});
    int nr_segments = segments.size ();
    for (Segment s : segments) {
       /// cout << s.a.first << " " << s.a.second << " " << s.b.first << " " << s.b.second << "\n";
        if (s.a.first == s.b.first) { /// x equal
            if (s.a.second > s.b.second)
                swap (s.a, s.b);
        }
        else {
            if (s.a.first > s.b.first) /// y equal
                swap (s.a, s.b);
        }
    }
    bool ok = true;
    for (int i = 0; i < nr_segments; i++)
        for (int j = i + 2; j < nr_segments; j++)
            if (doIntersect (segments[i].a, segments[i].b, segments[j].a, segments[j].b))
                ok = false;
    if (ok) {
        cout << "YES\n";
        for (int i = 1; i < n; i++)
            cout << length_hor[i] << " ";
        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: WRONG ANSWER

Test 3

Group: 1, 2, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 4, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 4, 5

Verdict: ACCEPTED

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: WRONG ANSWER

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: ACCEPTED

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: WRONG ANSWER