记录编号	613531	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4355.[省选联考 2026] 排列游戏	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	0.793 s
提交时间	2026-03-17 19:10:45	内存使用	5.30 MiB

#include <iostream>
#include <vector> 
#include "perm.h"

using namespace std;

/*
I often dwell on the past.
Moments in life become fixed in my mind. I cut, fold, curl, and knead the time behind me into clouds drifting in the sky.
Not all clouds are the same: cumulus clouds are heavy and full, while cirrus clouds are thin and ethereal. The stunning scenes in life flash across my thoughts and stay etched in my memory forever, whereas ordinary memories leave only faint fragments after being worn away by time. Recollection is like falling into a dream―too clear, and it spoils the pleasure of fantasy; too vague, and it sinks into emptiness. Only landscapes veiled in mist, a woman behind a veil, that perfect subtle haze, can satisfy my strict longing for beauty.
Before I know it, remembrance wraps me in yellowed pages. Friends who parted and reunited, streets torn down and rebuilt, all these clues lead me to trace back upstream along the river of time from a single moment. Days gone by can never return; I am but a passer-by. Yet I still wish to set aside quiet time on each journey into memory, to pause before a scene, to gaze at my former self through the haze of years, and to embrace as much sweetness as I can. Once beautiful moments have flowed through me, I am content.
The past has solidified. I carry my memories forward, yet I often fail to guard them carefully, and they gradually reshape themselves. This brings some difficulty to my journeys into recollection.
Where should I stop? I ask myself.
*/ 

void init (int c, int t) {
    return;
}

vector<int> perm (int n) {
    vector<int> res(n, -1);
    vector<int> pre(n);
    vector<int> suf(n);
    vector<int> vis(n);
    int pos = n - 1;
    
    for (int i = 0; i < n - 1; i++) {
    	pre[i] = query (i + 1, n - 1);
    	if (!pre[i]) {
    		pos = i;
    		for (int j = i + 1; j < n; j++) {
    			suf[j] = query (0, j - 1);
			}
			break;
		}
	}
	
	res[0] = pre[0];
	res[n - 1] = suf[n - 1];
	for (int i = 1; i < n - 1; i++) {
		if (pre[i] != pre[i - 1]) {
			res[i] = pre[i];
		}
		if (suf[i] != suf[i + 1]) {
			res[i] = suf[i];
		}
	}
	for (int i = 0; i < n; i++) {
		if (res[i] != -1) {
			vis[res[i]] = true;
		}
	}
	
	for (int l = 0, r = n - 1, i = n - 1; ; i--) {
		for (; i >= 0 && vis[i]; i--) {}
		if (i < 0) {
			break;
		}
		
		for (; l < pos && res[l] != -1; l++) {}
		for (; r > pos && res[r] != -1; r--) {}
		
		res[pre[l] > suf[r] ? l : r] = i;
		vis[i] = true;
	}
    
    return res;
}