oj.uz

Submission #941878

# Submission time Handle Problem Language Result Execution time Memory
941878 2024-03-09T15:48:07 Z abcvuitunggio Secret Permutation (RMI19_permutation) C++17
10 / 100
 3015 ms 344 KB 
//#define NAM
#ifndef NAM
#include "permutation.h"
#endif // NAM
#include <bits/stdc++.h>
using namespace std;
#ifdef NAM
int n,cnt_q=0;
vector <int> p,q;
int query(vector <int> v){
    auto v2=v;
    sort(v2.begin(),v2.end());
    int ch=1;
    for (int i=0;i<v2.size();i++)
        ch&=(v2[i]==i+1);
    if (v2.size()!=n||!ch){
        cout << "Error: Not a permutation";
        exit(0);
    }
    cnt_q++;
    int res=0;
    for (int i=0;i<n-1;i++)
        res+=abs(p[v[i]-1]-p[v[i+1]-1]);
    return res;
}
void answer(vector <int> v){
    if (v!=p&&v!=q)
        cout << "Wrong Answer";
    else{
        cout << "Correct\n";
        cout << "You asked " << cnt_q << " queries";
    }
}
#endif // NAM
void solve(int n){
    vector <int> cur;
    for (int i=1;i<=n;i++)
        cur.push_back(i);
    int x=query(cur);
    while (x>n-1){
        for (int i=0;i<n;i++)
            for (int j=i+1;j<n;j++){
                reverse(cur.begin()+i,cur.begin()+j+1);
                int y=query(cur);
                if (y<x)
                    x=y;
                else
                    reverse(cur.begin()+i,cur.begin()+j+1);
            }
    }
    vector <int> ans(n,0);
    for (int i=1;i<=n;i++)
        ans[cur[i-1]-1]=i;
    answer(ans);
}
#ifdef NAM
int main(){
    cin >> n;
    for (int i=1;i<=n;i++)
        p.push_back(i);
    random_shuffle(p.begin(),p.end());
    for (int i:p)
        q.push_back(n-i+1);
    solve(n);
}
#endif // NAM

Compilation message

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]
   15 |   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]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 344 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Partially correct 1 ms 344 KB Partially correct
5 Partially correct 1 ms 344 KB Partially correct
6 Partially correct 0 ms 344 KB Partially correct

Subtask #2
7.0 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 344 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Partially correct 1 ms 344 KB Partially correct
5 Partially correct 1 ms 344 KB Partially correct
6 Partially correct 0 ms 344 KB Partially correct
7 Partially correct 53 ms 344 KB Partially correct
8 Partially correct 42 ms 344 KB Partially correct
9 Partially correct 14 ms 344 KB Partially correct
10 Partially correct 25 ms 344 KB Partially correct
11 Partially correct 38 ms 340 KB Partially correct
12 Partially correct 20 ms 344 KB Partially correct
13 Partially correct 32 ms 344 KB Partially correct
14 Partially correct 26 ms 344 KB Partially correct
15 Partially correct 22 ms 344 KB Partially correct
16 Partially correct 38 ms 344 KB Partially correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 1 ms 344 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Partially correct 1 ms 344 KB Partially correct
5 Partially correct 1 ms 344 KB Partially correct
6 Partially correct 0 ms 344 KB Partially correct
7 Partially correct 53 ms 344 KB Partially correct
8 Partially correct 42 ms 344 KB Partially correct
9 Partially correct 14 ms 344 KB Partially correct
10 Partially correct 25 ms 344 KB Partially correct
11 Partially correct 38 ms 340 KB Partially correct
12 Partially correct 20 ms 344 KB Partially correct
13 Partially correct 32 ms 344 KB Partially correct
14 Partially correct 26 ms 344 KB Partially correct
15 Partially correct 22 ms 344 KB Partially correct
16 Partially correct 38 ms 344 KB Partially correct
17 Execution timed out 3015 ms 340 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -