Submission #239394

#	Time	Username	Problem	Language	Result	Execution time	Memory
239394		Sorting	Secret Permutation (RMI19_permutation)	C++14	100 / 100	2589 ms	544 KiB

permutation

#include <bits/stdc++.h>
//#include "permutationc.h"

using namespace std;

int query(int v[]);
int query(vector<int> v);
void answer(int v[]);
void answer(vector<int> v);

void recursion(const vector<int> &v, const vector<int> &arr, vector<int> &ans, vector<int> &vis, int pos){
    if(pos == v.size() - 1){
        if(abs(ans[0] - ans[v.size() - 1]) == arr[pos]){
            vector<int> x(v.size());
            for(int i = 0; i < v.size(); ++i)
                x[v[i] - 1] = ans[i];

            answer(x);
            exit(0);
        }
        return;
    }

    int choice1 = ans[pos] + arr[pos];
    int choice2 = ans[pos] - arr[pos];

    if(choice1 <= v.size() && !vis[choice1]){
        ans[pos + 1] = choice1;
        vis[choice1] = true;
        recursion(v, arr, ans, vis, pos + 1);
        ans[pos + 1] = 0;
        vis[choice1] = false;
    }
    if(choice2 >= 1 && !vis[choice2]){
        ans[pos + 1] = choice2;
        vis[choice2] = true;
        recursion(v, arr, ans, vis, pos + 1);
        ans[pos + 1] = 0;
        vis[choice2] = false;
    }
}

void solve(int n){
    vector<int> v;
    for(int i = 1; i <= n; ++i)
        v.push_back(i);

    mt19937 mt(7);
    random_shuffle(v.begin(), v.end(), [&](int mod){return mt() % mod;});

    vector<int> arr(n + 1);
    for(int i = 0; i < n; ++i){
        rotate(v.begin(), v.begin() + 1, v.end());
        arr[i] = query(v);
    }

    int sum = 0;
    for(int i = 0; i < n; ++i)
        sum += arr[i];
    sum /= n - 1;

    for(int i = 0; i < n; ++i)
        arr[i] = sum - arr[i];

    //for(int i = 0; i < n; ++i)
    //    cout << arr[i] << " ";
    //cout << endl;

    vector<int> ans(n), vis(n + 1, false);
    for(int i = 1; i <= n; ++i){
        ans[0] = i;
        vis[i] = true;
        recursion(v, arr, ans, vis, 0);
        ans[0] = 0;
        vis[i] = false;
    }
}

Compilation message (stderr)

permutation.cpp: In function 'void recursion(const std::vector<int>&, const std::vector<int>&, std::vector<int>&, std::vector<int>&, int)':
permutation.cpp:12:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos == v.size() - 1){
        ~~~~^~~~~~~~~~~~~~~
permutation.cpp:15:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); ++i)
                            ~~^~~~~~~~~~
permutation.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(choice1 <= v.size() && !vis[choice1]){
        ~~~~~~~~^~~~~~~~~~~
stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(stdin, "%d", &x);
   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(stdin, "%d", &N);
   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 50 / 50