QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #692913 | #91. Secret Permutation | HJY2022 | 15 | 1ms | 4096kb | C++20 | 1.1kb | 2024-10-31 15:12:48 | 2024-10-31 15:12:54 |
Judging History
answer
#include<bits/stdc++.h>
#include "permutation.h"
using namespace std;
const int MX = 305;
int a[MX],d[MX],ans[MX],id[MX];bool vis[MX];
bool dfs(int x,int p,int N,int mn,int mx){
if(mx - mn > N - 1 || vis[p + MX])return 0;
ans[x] = p;
if(x == N){
if(p - d[N] == 0 || p + d[N] == 0)return 1;
return 0;
}
vis[p + MX] = 1;
if(dfs(x + 1,p + d[x],N,mn,max(mx,p + d[x])))return 1;
if(dfs(x + 1,p - d[x],N,min(mn,p - d[x]),mx))return 1;
vis[p + MX] =0;
return 0;
}
void solve(int N){
vector<int > q;q.resize(N);
for(int i = 1;i <= N;i++)id[i] = i;
mt19937 rng(1984);shuffle(id + 1,id + 1 + N,rng);
for(int i = 0;i < N;i++)q[i] = id[i + 1];
a[0] = query(q);int sum = 0;
for(int i = 1;i < N;i++){
int p = 0;
for(int j = i;j >= 1;j--)q[p++] = id[j];
for(int j = N;j > i;j--)q[p++] = id[j];
a[i] = query(q);sum += a[i];
}
sum -= (N - 2) * a[0];sum /= (N - 1);
for(int i = 1;i < N;i++)d[i] = a[0] - a[i] + sum;d[N] = sum;
dfs(1,0,N,0,0);int mn = 1000000000;
for(int i = 1;i <= N;i++)mn = min(mn,ans[i]);
for(int i = 0;i < N;i++)q[id[i + 1] - 1] = ans[i + 1] - mn + 1;
answer(q);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 0ms
memory: 3772kb
input:
7 5 7 1 3 2 4 6
output:
0 7 1050790
result:
points 1.0 7 steps
Test #2:
score: 15
Accepted
time: 0ms
memory: 3808kb
input:
4 3 4 2 1
output:
0 4 0
result:
points 1.0 4 steps
Test #3:
score: 15
Accepted
time: 1ms
memory: 4096kb
input:
6 3 5 4 2 6 1
output:
0 6 0
result:
points 1.0 6 steps
Test #4:
score: 15
Accepted
time: 0ms
memory: 4000kb
input:
7 5 7 2 6 4 3 1
output:
0 7 0
result:
points 1.0 7 steps
Test #5:
score: 15
Accepted
time: 0ms
memory: 3800kb
input:
7 7 4 6 2 1 3 5
output:
0 7 9010
result:
points 1.0 7 steps
Test #6:
score: 15
Accepted
time: 0ms
memory: 3820kb
input:
7 1 2 6 5 4 7 3
output:
0 7 11756225322523
result:
points 1.0 7 steps
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #7:
score: 0
Wrong Answer
time: 1ms
memory: 3748kb
input:
50 33 8 50 28 6 40 15 17 22 11 30 32 23 10 27 48 13 16 29 24 43 44 9 45 47 4 5 25 42 41 2 14 21 35 19 12 7 36 1 46 26 3 49 34 18 20 37 31 38 39
output:
-1
result:
wrong answer Your answer is not correct.
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%