제출 #259628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259628		lyc	Secret Permutation (RMI19_permutation)	C++14	50 / 100	37 ms	504 KiB

permutation

#include "permutation.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;
using ii=pair<int,int>;

void solve(int N) {
	vector<int> V(N);
	iota(ALL(V),1);
	
	int mid;
	vector<ii> lh, rh;
	{
		int q1 = query(V);
		swap(V[0],V[1]);
		int q2 = query(V);
		swap(V[0],V[1]);
		
		swap(V[1],V[2]);
		int q3 = query(V);
		swap(V[0],V[1]);
		int q4 = query(V);
		swap(V[0],V[1]);
		swap(V[1],V[2]);
		
		swap(V[0],V[2]);
		swap(V[0],V[1]);
		int q5 = query(V);
		swap(V[0],V[1]);
		int q6 = query(V);
		swap(V[0],V[2]);
		
		if (q1-q2 > 0) {
			if (q3-q4 > 0) {
				mid = 1;
				lh = {ii(2,q1-q2)};
				rh = {ii(3,q3-q4)};
			} else {
				mid = 3;
				rh = {ii(1,q4-q3)};
				lh = {ii(2,q4-q3+(q1-q2))};
			}
		} else {
			if (q3-q4 > 0) {
				mid = 2;
				lh = {ii(1,q2-q1)};
				rh = {ii(3,q2-q1+(q3-q4))};
			} else {
				if (q5-q6 > 0) {
					mid = 2;
					rh = {ii(3,q5-q6)};
					lh = {ii(1,q2-q1)};
				} else {
					mid = 3;
					lh = {ii(2,q6-q5)};
					rh = {ii(1,q4-q3)};
				}
			}
		}
	}
	
	//~ for (auto x : lh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
	//~ for (auto x : rh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
	
	if (N > 3) {
		//~ TRACE(mid _ rh[0].first);
		FOR(i,0,N-1) if (V[i] == mid) swap(V[0],V[i]);
		FOR(i,0,N-1) if (V[i] == rh[0].first) swap(V[1],V[i]);
		FOR(i,3,N-1){
			swap(V[2],V[i]);
			int q1 = query(V);
			swap(V[0],V[1]);
			int q2 = query(V);
			swap(V[0],V[1]);
			
			if (abs(q2-q1) < rh[0].second) {
				//~ TRACE("R" _ (q2-q1+rh[0].second)/2);
				rh.push_back(ii(i+1,(q2-q1+rh[0].second)/2));
			} else {
				if (q2-q1 < 0) {
					swap(V[1],V[2]);
					int q3 = query(V);
					swap(V[0],V[1]);
					int q4 = query(V);
					swap(V[0],V[1]);
					swap(V[1],V[2]);
					//~ TRACE("L" _ q3-q4);
					lh.push_back(ii(i+1,q3-q4));
				} else {
					swap(V[0],V[2]);
					int q3 = query(V);
					swap(V[0],V[1]);
					int q4 = query(V);
					swap(V[0],V[1]);
					swap(V[0],V[2]);
					//~ TRACE("R" _ q4-q3);
					rh.push_back(ii(i+1,q4-q3+rh[0].second));
				}
			}
			swap(V[2],V[i]);
		}
	}
	
	sort(ALL(lh),[](ii a, ii b){ return a.second > b.second; });
	sort(ALL(rh),[](ii a, ii b){ return a.second < b.second; });
	
	vector<int> sorted;
	for (auto x : lh) sorted.push_back(x.first);
	sorted.push_back(mid);
	for (auto x : rh) sorted.push_back(x.first);
	
	vector<int> P(N);
	FOR(i,0,N-1) P[sorted[i]-1] = i+1;
	
	//~ for (auto x : sorted) { cout << x << ' '; } cout << endl;
	//~ for (auto x : lh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
	//~ for (auto x : rh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
	//~ for (int x : P) { cout << x << ' '; } cout << endl;
	
	answer(P);
}

컴파일 시 표준 에러 (stderr) 메시지

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]
   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]
   fscanf(stdin, "%d", &N);
   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 7.5 / 15
• Subtask 2: 17.5 / 35
• Subtask 3: 25 / 50