oj.uz

Submission #1054334

# Submission time Handle Problem Language Result Execution time Memory
1054334 2024-08-12T08:52:45 Z vjudge1 Secret Permutation (RMI19_permutation) C++17
0 / 100
 0 ms 344 KB 
#include "permutation.h"
#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 300;
 
namespace {
	long long D[maxn];
	bool vis[maxn];
	vector<int> crr;
	vector<vector<int>> allans;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
}
 
bool bt(int pos, int n, const vector<int> &P){
	if(pos > n){
		if(abs(crr.back() - crr[0]) != D[1])return false;
		vector<int> nw(n);
		for(int i = 0; i < n; i++){
			nw[P[i]-1] = crr[i];
		}
		crr = nw;
		return true;
	}
	int tmp = crr.back() + D[pos]; 
	if(tmp <= n && !vis[tmp]){
		crr.push_back(tmp);
		vis[tmp] = 1;
		if(bt(pos+1, n, P))return true;
		vis[tmp] = 0;
		crr.pop_back();
	}
	
	tmp = crr.back() - D[pos]; 
	if(tmp > 0 && !vis[tmp]){
		crr.push_back(tmp);
		vis[tmp] = 1;
		if(bt(pos+1, n, P))return true;
		vis[tmp] = 0;
		crr.pop_back();
	}
	return false;
}
 
void solve(int N) {
	long long sum = 0;
	vector<int> P(N);
	iota(P.begin(), P.end(), 1);
	shuffle(P.begin(), P.end(), rng);
	for(int i = 1; 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 = 1; i <= N; i++){
		D[i] = sum - D[i];
		// cout << D[i] << endl;
	}
	allans.clear();
 
	for(int i = 1; i <= N; i++){
		crr.push_back(i);
		vis[i] = 1;
		if(bt(2, N, P)){
			answer(crr);
			return;
		}
		vis[i] = 0;
		crr.pop_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
0.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 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.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 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.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 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -