oj.uz

Submission #1008821

# Submission time Handle Problem Language Result Execution time Memory
1008821 2024-06-26T20:59:40 Z box Secret Permutation (RMI19_permutation) C++17
100 / 100
 957 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(v.size())
typedef long long ll;

const int mxN=256;

#ifndef LOCAL
#include "permutation.h"
#else
int n, p[mxN];
int query(vector<int> v) {
    int x=0;
    assert(sz(v)==n);
    for (int i=0; i<n-1; i++) x+=abs(p[v[i+1]-1]-p[v[i]-1]);
    return x;
}
void answer(vector<int> v) {
    assert(sz(v)==n);
    for (int i=0; i<n; i++) cout<<v[i]<<" \n"[i==n-1];
}

#endif

int N, o[mxN];
int r[mxN];
mt19937 rng(2);
bool used[mxN*2+1];
int a[mxN];

bool rec(int i, int low, int hi) {
    if (hi-low+1>N) return 0;
    if (i==N-1) {
        if (abs(r[N-1])!=abs(a[0]-a[N-1])) return 0;
        int v=*min_element(a,a+N);
        for (int i=0; i<N; i++) a[i]=a[i]-v+1;
        return 1;
    }
    int x=a[i];
    if (x+r[i]<=N*2&&x+r[i]>=0&&!used[x+r[i]]) {
        used[a[i+1]=x+r[i]]=1;
        if (rec(i+1,min(low,a[i+1]),max(hi,a[i+1]))) return 1;
        used[a[i+1]]=0;
    }
    if (x-r[i]<=N*2&&x-r[i]>=0&&!used[x-r[i]]) {
        used[a[i+1]=x-r[i]]=1;
        if (rec(i+1,min(low,a[i+1]),max(hi,a[i+1]))) return 1;
        used[a[i+1]]=0;
    }
    return 0;
}

int gen(int l, int r) {
    return uniform_int_distribution(l,r)(rng);
}

void solve(int n) {
    N=n;
    iota(o,o+N,1);
    for (int i=0; i<N; i++) swap(o[i],o[gen(0,i)]);
    for (int i=0; i<N; i++) {
        rotate(o,o+1,o+N);
        r[i]=query(vector(o,o+N));
    }
    for (int i=0; i<N; i++) o[i]--;
    int s=accumulate(r,r+N,0);
    assert(s%(N-1)==0);
    s/=N-1;
    for (int i=0; i<N; i++) r[i]=s-r[i];
    fill(used,used+N*2+1,0);
    used[a[0]=N]=1;
    assert(rec(0,N,N));
    vector<int> v(N);
    for (int i=0; i<N; i++) v[o[i]]=a[i];
    answer(v);
}

#ifdef LOCAL
int main() {
    cin>>n;
    for (int i=0; i<n; i++) cin>>p[i];
    solve(n);
}
#endif

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
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 412 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 412 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 14 ms 444 KB Output is correct
18 Correct 8 ms 440 KB Output is correct
19 Correct 36 ms 440 KB Output is correct
20 Correct 8 ms 344 KB Output is correct
21 Correct 6 ms 448 KB Output is correct
22 Correct 5 ms 440 KB Output is correct
23 Correct 957 ms 344 KB Output is correct
24 Correct 6 ms 600 KB Output is correct
25 Correct 12 ms 444 KB Output is correct
26 Correct 13 ms 432 KB Output is correct