Submission #259616

#	Time	Username	Problem	Language	Result	Execution time	Memory
259616		cheeheng	Secret Permutation (RMI19_permutation)	C++14	3 / 100	3705 ms	384 KiB

permutation

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

int tempV[10005][505];
int temp[10005];

typedef pair<int, int> ii;
ii R[100005];

void solve(int N){
    vector<int> V;
    vector<int> P;
    for(int i = 1; i <= N; i ++){
        V.push_back(i);
        P.push_back(i);
    }

    int cnt = 0;
    for(int i = 0; i < N; i ++){
        for(int j = i+1; j < N; j ++){
            R[cnt++] = ii(i, j);
        }
    }

    if(N > 0){
        while(true){
            int bestI = -1;
            int bestJ = -1;
            int minVal = N*N+5;
            random_shuffle(R, R+cnt);
            for(int k = 0; k < cnt; k ++){
                int i, j;
                tie(i, j) = R[k];
                //printf("Considered: %d %d\n", i, j);
                swap(V[i], V[j]);
                int temp = query(V);
                if(temp < minVal){
                    minVal = temp;
                    bestI = i;
                    bestJ = j;
                }

                swap(V[i], V[j]);
            }

            swap(V[bestI], V[bestJ]);
            if(minVal == N-1){break;}
        }

        for(int i = 0; i < N; i ++){
            P[V[i]-1] = i+1;
        }
        answer(P);
    }

    //printf("P.size() = %d\n", (int)P.size());

    for(int i = 0; i < N; i ++){
        random_shuffle(V.begin(), V.end());
        temp[i] = query(V);
        for(int j = 0; j < N; j ++){
            tempV[i][j] = V[j];
        }
    }

    sort(P.begin(), P.end());

    do{
        bool boleh = true;
        for(int j = 0; j < N; j ++){
            int tempAns = 0;
            for(int i = 0; i < N-1; i ++){
                tempAns += abs(P[tempV[j][i]-1] - P[tempV[j][i + 1]-1]);
            }
            if(tempAns != temp[j]){
                boleh = false;
                break;
            }
        }

        if(boleh){
            answer(P);
        }
    }while(next_permutation(P.begin(), P.end()));


    return;
}

Compilation message (stderr)

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: 3 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 50