oj.uz

답안 #940598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940598 2024-03-07T11:23:17 Z marvinthang Secret Permutation (RMI19_permutation) C++17
100 / 100
 1303 ms 688 KB 
/*************************************
*    author: marvinthang             *
*    created: 19.03.2023 14:18:40    *
*************************************/
// https://oj.uz/problem/view/RMI19_permutation

#include "permutation.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
		#include "debug.h"
#else
		#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
		#define DB(...) 23
		#define db(...) 23
		#define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); } 
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); } 

vector <bool> used;
vector <long long> d;
vector <int> res;

bool backtracking(int i, int n) {
	if (i == n) return abs(res[0] - res[n - 1]) == d[0];
	if (!i) {
		REP(j, n) {
			res[i] = j;
			used[j] = true;
			if (backtracking(i + 1, n)) return true;
			used[j] = false;
		}
	} else {
		int x = res[i - 1] + d[i];
		if (x < n && !used[x]) {
			res[i] = x;
			used[x] = true;
			if (backtracking(i + 1, n)) return true;
			used[x] = false;
		}
		x = res[i - 1] - d[i];
		if (x >= 0 && !used[x]) {
			res[i] = x;
			used[x] = true;
			if (backtracking(i + 1, n)) return true;
			used[x] = false;
		}
	}
	return false;
}

void solve(int n) {
	vector <int> v(n);
	iota(ALL(v), 1);
	REP(_, 10) shuffle(ALL(v), rng);
	d.resize(n);
	long long total = 0;
	REP(i, n) {
		d[i] = query(v);
		total += d[i];
		rotate(v.begin(), v.begin() + 1, v.end());
	}
	total /= n - 1;
	REP(i, n) d[i] = total - d[i];
	used.assign(n, 0);
	res.resize(n);
	backtracking(0, n);
	vector <int> ans(n);
	REP(i, n) ans[v[i] - 1] = res[i] + 1;
	answer(ans);
}

#ifdef LOCAL

namespace A {
	int N;
	const int MAX_N = 1000;
	int P[1 + MAX_N];
	int queries = 0;
	
	void readInput() {
		//printf("The permutation you have to guess is:\n");
		scanf("%d", &N);
		for (int i = 1; i <= N; i++) {
			// P[i] = i;
			scanf("%d", &P[i]);
			//printf("%d ", P[i]);
		}
		// shuffle(P + 1, P + 1 + N, rng);
		//printf("\n");
	}
	
	int query(int V[]) {
		queries++;
		printf("query(");
		for (int i = 0; i < N - 1; i++) {
			printf("%d, ", V[i]);
		}
		printf("%d) = ", V[N - 1]);
		int freq[1 + N];
		for (int i = 0; i <= N; i++) {
			freq[i] = 0;
		}
		for (int i = 0; i < N; i++) {
			freq[V[i]]++;
		}
		for (int i = 1; i <= N; i++) {
			assert(freq[i] == 1);
		}
		int answer = 0;
		for (int i = 0; i + 1 < N; i++) {
			answer += abs(P[V[i + 1]] - P[V[i]]);
		}
		printf("%d\n", answer);
		fflush(stdout);
		return answer;
	}

	void answer(int V[]) {
		bool ok = true;
		for (int i = 1; i <= N; i++) {
			ok &= (V[i - 1] == P[i]);
		}
		if (ok) {
			printf("Correct! with N = %d, Q = %d\n", N, queries);
		} else {
			printf("Wrong answer!\n");
		}
		exit(0);
	}
}

int query(int p[]) {
	return A::query(p);
}

void answer(int ans[]) {
	A::answer(ans);
}

int query(std::vector<int> v) {
	int array[A::N];
	for (int i = 0; i < A::N; i++) {
		array[i] = v[i];
	}
	return query(array);
}

void answer(std::vector<int> v) {
	int array[A::N];
	for (int i = 0; i < A::N; i++) {
		array[i] = v[i];
	}
	answer(array);
}

int main() {
	file("PERMUTATION");
	A::readInput();
	solve(A::N);
	return 0;
}
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 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

# 결과 실행 시간 메모리 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 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 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 6 ms 448 KB Output is correct
18 Correct 221 ms 444 KB Output is correct
19 Correct 210 ms 444 KB Output is correct
20 Correct 19 ms 444 KB Output is correct
21 Correct 22 ms 688 KB Output is correct
22 Correct 5 ms 444 KB Output is correct
23 Correct 201 ms 444 KB Output is correct
24 Correct 185 ms 448 KB Output is correct
25 Correct 10 ms 448 KB Output is correct
26 Correct 1303 ms 444 KB Output is correct