2615. [FHZOI 2017]映射关系

【题目描述】

传说中的交互式题目来也（可惜是个水题233）（用评测插件实现的，请大家自觉遵守规定QwQ利用漏洞骗分是可耻的行为）

第一，你并不用在意I/O文件名，因为按照规则你并不被允许读写文件，这里也不会告诉你文件格式233333333

第二，普及一下啥叫交互式题目：

    一般来说是提供一个库文件/头文件供程序引用，其中包含一些类方法（然而COGS对其的支持基本可以吔屎(╯‵□′)╯︵┻━┻），包括初始化、询问、提交等。你的程序需要从这些类方法而不是文件中获取信息。

    其次，交互式题目除了时间限制、内存限制之外往往有调用次数限制并根据你的调用次数给分（COGS对于不同分数的支持也可以吔屎了(╯‵□′)╯︵┻━┻）。

第三，介绍一下题目内容

    一共有$N$个初始端，编号为1..N。每个初始端都有一个对应的映射端。不同的初始端不会有同一个映射端。但是出于某些原因你不能直接调查每个初始端对应的映射端，你只能得到这样的信息：初始端1 4 5 8对应的映射端是3 7 5 9。你并不能得到具体对应关系，也就是说回答是无序的。

【交互方法】

交互库提供一个包含3个类方法的Interacitve类，其中包含的可供选手调用的方法如下：

int Initialize();

int* Quest(int*);

void Submit(int*);

（没错，此题是Pascal不友好的）

首先请在程序开头调用Initialize方法，该方法返回1个int值，为$N$。你只能调用一次否则就会异常退出。

Quest方法接收一个int指针（其实就是你想询问映射关系的数组$A_0..m$），该数组第0位是你想询问映射关系的数量$m$。此后的$m$个元素为你想询问的映射关系的初始端。该方法返回一个指向存储对应映射端的数组$B_0..m-1$。为了方便使用，该方法返回的数组已经按升序排好。

Submit方法接收一个指向数组$S_0..N$的指针。$S_0$应置为0，$S_i$表示计算得的初始端$i$对应的映射端。

调用示例：

int n=Inter.Initialize();

Inter.Submit(ans);

【交互示例】

以下为成功交互的一个例子，但显然并不是正解（以下代码已略去交互库部分）

/*<Interactive Library>*/
int main(){
    int n=Inter.Initialize();    
    int ans[n]={0};
    int q[]={5,1,6,8,2,3};
    int* r=Inter.Quest(q);
    for(int i=0;i<5;i++){
        ans[r[i]]=q[i+1];
    }
    Inter.Submit(ans);
    return 0;
}

【评分标准】

设出题人的标程可达到的最小询问次数为$S$，你的询问次数为$S_x$，则按照如下规则判分：

$S_x<S$ Score=12;

$S_x==S$ Score=10;

$S_x<=S+1$ Score=9;

$S_x<=S+2$ Score=8;

$S_x<=S+3$ Score=7;

$S_x<=S+5$ Score=6;

$S_x<=S+10$ Score=5;

$S_x<=2S$ Score=4;

$S_x<=3S$ Score=3;

$S_x<=5S$ Score=2;

$S_x<=10S$ Score=1;

$S_x>10S$ Score=0;

【提示】

请在提交的代码前加入如下代码（警告：不要擅自拆封或修改其中的代码）：

%:include <bits/stdc++.h>
using namespace std;class Interactive<%private:static const int _=10010;bool __;int ___;int ____<:_:>;int _____<:_:>;int ______<:100:>;int _____________;void _______()<%FILE* ________=fopen("Interactive.in","rb");fread(______,sizeof(int),100,________);fread(&_____________,sizeof(int),1,________);fread(_____+1,sizeof(int),_____________,________);fclose(________);%>void _________()<%for(int ___________=0,____________=1;____________<=_____________;____________++,___________=___________<99?___________+1:0)<%_____<:____________:>=_____<:____________:>^______<:___________:>;%>%>void ___________________________(int* ___________________)<%for(int ___________=0,____________=1;____________<=_____________;____________++,___________=___________<99?___________+1:0)<%___________________<:____________:>=___________________<:____________:>^______<:___________:>;%>%>void ______________(int* _______________)<%FILE* ________________=fopen("Interactive.out","wb");int _________________=0;fwrite(&_________________,sizeof(int),1,________________);fwrite(&_____________,sizeof(int),1,________________);fwrite(_______________+1,sizeof(int),_____________,________________);fwrite(&___,sizeof(int),1,________________);fclose(________________);%>public:int Initialize()<%int _________________=0xFFFFFFFF;if(__)exit(233);_______();_________();FILE* ________________=fopen("Interactive.out","wb");fwrite(&_________________,sizeof(int),1,________________);fclose(________________);__=true;return _____________;%>int* Quest(int* q)<%memset(____,0,sizeof(____));for(int ___________=1;___________<=q<:0:>;___________++)<%____<:___________-1:>=_____<:q<:___________:>:>;%>sort(____,____+q<:0:>);___++;return ____;%>void Submit(int* ___________________)<%___________________________(___________________);______________(___________________);exit(0);%>%>Inter;

【数据范围】

100% n<=10000,保证所有的的映射端为1~n的排列。

【来源】

Albert S. Chang

FHZOI 2017