1608B - Build the Permutation - CodeForces Solution


constructive algorithms greedy *1200

Please click on ads to support us..

Python Code:

t = int(input())

for i in range(t):

    n, a, b = map(int, input().split())

    c = [j + 1 for j in range(n)]

    ans = []

    if a + b > n - 2 or abs(a-b) > 1:
        print(-1)
    else:
        if b > a:
            for j in range(min(a,b) + 1):
                ans.append(c[-1])
                ans.append(c[0])
                c.pop()
                c.pop(0)
            ans += c

        elif a > b:
            for j in range(min(a, b) + 1):
                ans.append(c[0])
                ans.append(c[-1])
                c.pop(0)
                c.pop()
            c.reverse()
            ans += c

        else:
            for j in range(a):
                ans.append(c[0])
                ans.append(c[-1])
                c.pop(0)
                c.pop()
            ans.append(c[0])
            c.pop(0)
            ans += c

        for j in range(len(ans)):
            print(ans[j], end = ' ')
        print()






C++ Code:

#define ll long long
#define MAXN 200010
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;

int main(){
#ifdef _DEBUG
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif
#define int ll
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;
        vector<int> v;
        int i = 1, j = n;
        while (i < j) {
            v.push_back(i);
            v.push_back(j);
            ++i, --j;
        }
        if (i == j) {
            v.push_back(i);
        }
        int up = 0, down = 0;
        if (up == a && down == b) {
            sort(v.begin(), v.end());
            for (int i = 0; i < n; ++i) {
                cout << v[i] << " \n"[i == n - 1];
            }
            goto next;
        }
        for (int i = 1; i < (int) v.size() - 1; ++i) {
            if (v[i] > v[i-1] && v[i] > v[i+1]) {
                ++up;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    reverse(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
            else if (v[i] < v[i-1] && v[i] < v[i+1]) {
                ++down;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
        }
        v.clear();
        i = 1, j = n;
        while (i < j) {
            v.push_back(j);
            v.push_back(i);
            ++i, --j;
        }
        if (i == j) {
            v.push_back(i);
        }
        up = 0, down = 0;
        for (int i = 1; i < (int) v.size() - 1; ++i) {
            if (v[i] > v[i-1] && v[i] > v[i+1]) {
                ++up;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    reverse(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
            else if (v[i] < v[i-1] && v[i] < v[i+1]) {
                ++down;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
        }
        cout << "-1\n";
    next:;
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1487A - Arena
1520D - Same Differences
376A - Lever
1305A - Kuroni and the Gifts
1609A - Divide and Multiply
149B - Martian Clock
205A - Little Elephant and Rozdil
1609B - William the Vigilant
978B - File Name
1426B - Symmetric Matrix
732B - Cormen --- The Best Friend Of a Man
1369A - FashionabLee
1474B - Different Divisors
1632B - Roof Construction
388A - Fox and Box Accumulation
451A - Game With Sticks
768A - Oath of the Night's Watch
156C - Cipher
545D - Queue
459B - Pashmak and Flowers
1538A - Stone Game
1454C - Sequence Transformation
165B - Burning Midnight Oil
17A - Noldbach problem
1350A - Orac and Factors
1373A - Donut Shops
26A - Almost Prime
1656E - Equal Tree Sums
1656B - Subtract Operation
1656A - Good Pairs