有一個長度為 $N$ 的 $0\sim N-1$ 的排列 $p_0,p_1,\dots p_{N-1}$($0 \le p_i \le N-1$)。PCC 忘記這個排列的順序了,於是唯一記得順序的 becaido 說道:「你是一個一個一個」,表示他記得任何三個位置 $i,j,k$(可以重複)的數字中,最小以及次小兩者的 xor 值。
也就是說,對於任意的 $i,j,k$ ,且令 $p_i \le p_j \le p_k$ ,Caido 可以回答你 $p_i \oplus p_j$。但是,Caido 不想回答你太多次,不然他會去路上隨便找人跟他說:「你是一個一個一個」。因此,請在不問 Caido 超過 $140000$ 次的情況下找出這個排列吧。
本題為互動題,並會根據你問 Caido 的總次數進行給分。
給分公式如下:
假設你總共問了 Caido $q$ 個問題,那在該筆測試資料你獲得的比例為 $0.2+0.8 \times \min(1,10050/q)$。
對於一個子題,你所得到的分數為所有測試資料中的比例最小值乘上該子題的配分。
本題的 judge 為 non-adaptive,也就是說,測試資料在互動開始前就已經決定好,不會根據你的詢問而有所改變。
本題是互動題,請在程式碼的開頭引入標頭檔 #include "lib2382.h"
,程式碼請勿輸入或輸出任何東西。如果你輸入了任何東西可能會導致各種不可預期的結果。
可以呼叫以下函式:
int Init()
:請在開頭呼叫本函式一次,回傳值為一個正整數 $N$,代表這個排列的長度。對於所有測試資料:$1 \leq N \leq 10 ^ 4 $
int Ask(int a, int b,int c)
:輸入為三個整數 $a, b,c$,其中須符合 $0 \leq a, b,c \leq N-1$,回傳為一個整數,代表三個位置 $a,b,c$ 的數字 $p_a,p_b,p_c$ 當中最小與次小的 xor 值。如果你呼叫了 Ask
超過 $140000$ 次,你將會獲得 $0$ 分。
void Answer(vector<int> v)
:輸入為一個長度為 $N$ 的 vectorWA
。如果你沒有拿到滿分的話,你會得到 WA
以及部份分數。請在呼叫本函式之後終止程式。
本題沒有任何輸出。
以下是一個可以編譯(但一定不會答對)的範例程式碼:
#include <vector>
#include "lib2382.h"
using namespace std;
int main() {
int n = Init();
int q = Ask(0,n-1,0);
vector<int> v(n);
for(int i =0;i<n;i++)
v[i] = i;
Answer(v);
return 0;
}
以下是範例 grader,可以複製貼上並將檔案命名為 "lib2382.h",將其與你的程式放在同一個目錄下。
grader 會在第一行輸出 Answer
時的排列長度,第二行輸出排列,第三行輸出 $q$。
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
namespace GRADER{
const int lim = 140000;
vector<int> v;
int cnt = 0;
int n;
void Init(){
assert(1 == scanf("%d", &n));
v = vector<int>(n);
for(int i = 0;i<n;i++)assert(1 == scanf("%d",&v[i]));
}
int Ask(int a,int b,int c){
if(a<0||a>=n||b<0||b>=n||c<0||c>=n){
puts("Out of Range!\n");
exit(0);
}
cnt++;
if(cnt>lim){
puts("Too Many Queries!\n");
exit(0);
}
if(v[a]>=max(v[b],v[c]))return v[b]^v[c];
else if(v[b]>=max(v[a],v[c]))return v[a]^v[c];
else return v[a]^v[b];
}
}
int Ask(int a,int b,int c){return GRADER::Ask(a,b,c);}
int Init(){GRADER::Init();return GRADER::n;}
void Answer(vector<int> v){
printf("%d\n",(int)v.size());
for(auto &i:v)printf("%d ",i);
printf("\n%d",GRADER::cnt);
}
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~9, 32~35 | $N \le 10$ | 20 |
2 | 0~35 | $N \le 10000$ | 80 |