TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

59.1% (13/22)

Submission's AC Ratio

18.6% (18/97)

Tags

Description

有一個長度為 $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,也就是說,測試資料在互動開始前就已經決定好,不會根據你的詢問而有所改變。

Input Format

本題是互動題,請在程式碼的開頭引入標頭檔 #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$ 的 vector v ,代表你的答案,如果不滿足 $|v| = N$,或是 $v$ 不是一個排列,又或者 $v\neq p$ 代表你答錯了,你將獲得 $0$ 分以及 WA。如果你沒有拿到滿分的話,你會得到 WA 以及部份分數。請在呼叫本函式之後終止程式。

Output Format

本題沒有任何輸出。

Sample Input 1

Sample Output 1

Hints

以下是一個可以編譯(但一定不會答對)的範例程式碼:

#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;
}

Problem Source

以下是範例 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);
}

Subtasks

No. Testdata Range Constraints Score
1 0~9, 32~35 $N \le 10$ 20
2 0~35 $N \le 10000$ 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2
1 1000 131072 65536 1 2
2 1000 131072 65536 1 2
3 1000 131072 65536 1 2
4 1000 131072 65536 1 2
5 1000 131072 65536 1 2
6 1000 131072 65536 1 2
7 1000 131072 65536 1 2
8 1000 131072 65536 1 2
9 1000 131072 65536 1 2
10 1000 131072 65536 2
11 1000 131072 65536 2
12 1000 131072 65536 2
13 1000 131072 65536 2
14 1000 131072 65536 2
15 1000 131072 65536 2
16 1000 131072 65536 2
17 1000 131072 65536 2
18 1000 131072 65536 2
19 1000 131072 65536 2
20 1000 131072 65536 2
21 1000 131072 65536 2
22 1000 131072 65536 2
23 1000 131072 65536 2
24 1000 131072 65536 2
25 1000 131072 65536 2
26 1000 131072 65536 2
27 1000 131072 65536 2
28 1000 131072 65536 2
29 1000 131072 65536 2
30 1000 131072 65536 2
31 1000 131072 65536 2
32 1000 131072 65536 1 2
33 1000 131072 65536 1 2
34 1000 131072 65536 1 2
35 1000 131072 65536 1 2