/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 74ms 2.953 MiB
#3 Accepted 82ms 3.191 MiB
#4 Accepted 7ms 536.0 KiB
#5 Accepted 8ms 532.0 KiB
#6 Accepted 6ms 580.0 KiB
#7 Accepted 10ms 532.0 KiB
#8 Accepted 152ms 6.668 MiB
#9 Accepted 148ms 7.719 MiB
#10 Accepted 194ms 10.328 MiB
#11 Accepted 281ms 12.84 MiB
#12 Accepted 281ms 12.789 MiB
#13 Accepted 276ms 12.992 MiB
#14 Accepted 275ms 12.812 MiB
#15 Accepted 251ms 12.012 MiB
#16 Accepted 250ms 12.086 MiB
#17 Accepted 208ms 10.863 MiB
#18 Accepted 83ms 5.316 MiB
#19 Accepted 30ms 1.176 MiB

Code

#include <bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> path;

// Depth-first search to build the path
bool dfs(int pos) {
    if (pos == N) return true;
    int last = path[pos-1];
    for (int v : adj[last]) {
        if (!visited[v]) {
            visited[v] = true;
            path[pos] = v;
            if (dfs(pos+1)) return true;
            visited[v] = false;
        }
    }
    return false;
}

// Find one valid “beautiful” permutation for 1..N or return empty on failure
vector<int> find_beautiful_permutation(int N) {
    adj.assign(N+1, {});
    // build graph: edge u–v if gcd(u,v)==1 and |u−v|>1
    for (int u = 1; u <= N; ++u) {
        for (int v = u+1; v <= N; ++v) {
            if (abs(u - v) > 1 && __gcd(u, v) == 1) {
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
    }
    // sort neighbors by ascending degree to help prune early
    for (int u = 1; u <= N; ++u) {
        sort(adj[u].begin(), adj[u].end(),
             [&](int a, int b){ return adj[a].size() < adj[b].size(); });
    }

    visited.assign(N+1, false);
    path.assign(N, 0);

    // try every possible start
    for (int start = 1; start <= N; ++start) {
        visited[start] = true;
        path[0] = start;
        if (dfs(1)) {
            return path;
        }
        visited[start] = false;
    }
    return {};  // no solution
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> N;
        // impossible small cases
        if (N==2 || N==3 || N==4 || N==6) {
            cout << -1 << "\n";
            continue;
        }
        auto sol = find_beautiful_permutation(N);
        if (sol.empty()) {
            cout << -1 << "\n";
        } else {
            for (int x : sol) {
                cout << x << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1203 D. Roy Loves Permutation
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-16 21:14:56
Judged At
2025-07-16 21:14:56
Judged By
Score
100
Total Time
281ms
Peak Memory
12.992 MiB