oj.uz

답안 #1054317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1054317 2024-08-12T08:42:58 Z vjudge1 Secret Permutation (RMI19_permutation) C++17
70 / 100
 12 ms 456 KB 
#include "permutation.h"
#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 300;
 
namespace {
	long long D[maxn], DP[maxn];
	int p, n;
	bool vis[maxn];
	vector<int> crr;
	vector<vector<int>> allans;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	bool check(int val, int pos){
		if(vis[val] || val < 1 || val > n)return false;
		if(n > 50){
			if((pos+p)%n < pos && abs(val - crr[(pos+p)%n]) != DP[(pos+p)%n])return false;
			if((pos+n-p)%n < pos && abs(val - crr[(pos+n-p)%n]) != DP[pos])return false;
		}
		if(pos == n-1 && abs(crr[0] - val) != D[0])return false;
		return true;
	}
}
 
void bt(int pos){
	if(pos == n){
		allans.push_back(crr);
		return;
	}
	int tmp = crr.back() + D[pos]; 
	if(check(tmp, pos)){
		crr.push_back(tmp);
		vis[tmp] = 1;
		bt(pos+1);
		vis[tmp] = 0;
		crr.pop_back();
	}
	
	tmp = crr.back() - D[pos]; 
	if(check(tmp, pos)){
		crr.push_back(tmp);
		vis[tmp] = 1;
		bt(pos+1);
		vis[tmp] = 0;
		crr.pop_back();
	}
}
 
void solve(int N) {
	n = N;
	long long sum = 0;
	vector<int> P(N);
	for(int i = 2; i <= N; i++){
		if(__gcd(i, N) == 1){
			p = i;
			break;
		}
	}
	iota(P.begin(), P.end(), 1);
	for(int i = 0; i < N; i++){
		D[i] = query(P);
		sum += D[i];
		P.push_back(P[0]);
		P.erase(P.begin());
	}
 
	sum /= N-1;
	for(int i = 0; i < N; i++){
		D[i] = sum - D[i];
		// cout << D[i] << endl;
	}
	if(n > 50){
		sum = 0;
		for(int i = 0; i < N; i++)P[i] = i*p%N  + 1;
		for(int i = 0; i < N; i++){
			DP[P[0]-1] = query(P);
			sum += DP[P[0]-1];
			P.push_back(P[0]);
			P.erase(P.begin());
		}
		sum/=N-1;
		for(int i = 0; i < N; i++){
			DP[i] = sum - DP[i];
		}
	}
	allans.clear();
 
	for(int i = 1; i <= N; i++){
		crr.push_back(i);
		vis[i] = 1;
		bt(1);
		vis[i] = 0;
		crr.pop_back();
	}
	while(allans.size() > 2){
		shuffle(P.begin(), P.end(), rng);
		vector<vector<int>> nw;
		int chksum = query(P);
		for(auto vec: allans){
			int csum = 0;
			for(int i = 1; i < N; i++)csum += abs(vec[P[i]-1] - vec[P[i-1]-1]);
			if(csum == chksum)nw.push_back(vec);
		}
		allans = nw;
	}
	answer(allans.back());
 
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 0 ms 344 KB Partially correct
3 Correct 1 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
28.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 0 ms 344 KB Partially correct
3 Correct 1 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 0 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 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 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 0 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct

Subtask #3
30.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 0 ms 344 KB Partially correct
3 Correct 1 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 0 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 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 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 0 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Partially correct 7 ms 424 KB Partially correct
18 Partially correct 7 ms 344 KB Partially correct
19 Partially correct 8 ms 456 KB Partially correct
20 Partially correct 12 ms 444 KB Partially correct
21 Partially correct 7 ms 344 KB Partially correct
22 Partially correct 7 ms 344 KB Partially correct
23 Partially correct 9 ms 344 KB Partially correct
24 Partially correct 7 ms 344 KB Partially correct
25 Partially correct 9 ms 440 KB Partially correct
26 Partially correct 7 ms 344 KB Partially correct