当前位置：首页 > news >正文

打卡信奥刷题（3329）用C++实现信奥题 P9311 [EGOI 2021] Twin Cookies / 姐妹分饼干

news 2026/5/28 17:22:24

P9311 [EGOI 2021] Twin Cookies / 姐妹分饼干

题目背景

Day 1 Problem C.

题面译自 EGOI2021 twincookies。

本题官方没给交互库，由于交互库实现原因，数据可能较弱。如果您会写自适应交互库，可以与 rui_er 取得联系。

题目描述

本题是一道 I/O 交互题。

索菲在准备她们姐妹的生日派对。她们都喜欢饼干。这次生日，她们准备尝试一些新东西：不同饼干口味公司（UCTC）生产的饼干。

UCTC 生产的每一个饼干都有一个在1 11到10 16 10^{16}1016之间的整数美味度。索菲姐妹会嫉妒彼此，因此她们收到的饼干的总美味度必须相同。

UCTC 只接受恰好n nn个饼干的订单。在每个订单中，顾客详细说明他们想要的每个饼干的美味度。

顾名思义，不同饼干口味公司拒绝为同一个顾客生产两块美味度相同的饼干。索菲必须确保她从不订购同一种美味度两次——不管是同一个订单或者两个不同的订单。索菲以前从来没有从 UCTC 订购过，所以她可以购买每种口味的饼干最多一次。

还有一件事阻碍着索菲：众所周知 UCTC 的物流服务极为糟糕。当一个顾客订购n nn个饼干，只有其中一个会被送达。其余的饼干都被物流的员工偷吃了。顾客无法决定到底哪块饼干会被送达。

鉴于生日临近，索菲只有时间订购至多101 101101次。你的任务是帮助她。

具体地，你需要做的事情如下：

首先，订购饼干。你可以订购至多101 101101次，每次包含恰好n nn个想要的美味度。你可以分多次订购。在每笔订单发出后，你会立刻知道送达的饼干的美味度。
请记住你不能多次订购同一个美味度的饼干，即使在不同订单中也不行。（特别地，如果你订购了一些美味度的饼干但没有送达，你也不能重复订购同一美味度的饼干。）
然后，分饼干。当你收到足够多饼干的时候，你应该给姐妹分配一些饼干。每个人应该收到至少一个饼干，并且她们收到的饼干的总美味度应该相同。你不需要分配所有送达的饼干。

输入格式

无

输出格式

你的程序每次输出后，你必须刷新输出流。为了保证交互库立即得到你的输出，这是必须的。

一些例子：

在 C++ 语言中，有多种选择：
- fflush(stdout);
- std::cout << std::flush;
- std::cout << std::endl;（注意这会打印一个换行）
- 从std::cin读入也会刷新输出流。
在 Java 语言中，你可以使用System.out.flush()
在 Python 语言中，你可以使用sys.stdout.flush()

交互方式

你的程序应该进行如下的若干操作：

从标准输入读入n nn。
至多101 101101次：
1. 首先，向标准输出打印一行描述n nn个饼干的一个订单。
2. 然后，输入送达的饼干美味度。
  保证这个数在当前订单的n nn个美味度当中。
输出三行，描述一种给姐妹分配一些饼干的方式。

交互库会在每一行写一个整数。

为了订购饼干，输出一行，以?打头并跟着n nn个整数：订购的饼干美味度。在每个整数之前输出一个空格。

请记住你可以订购至多101 101101次，并且不被允许多次订购相同美味度的饼干。

当你订购了足够多的饼干的时候，输出最后三行描述分配方式。

第一行的格式是! m k，其中m , k > 0 m,k>0m,k>0：两个人分别分到饼干的数量。

第二行包含m mm个正整数，用一个空格隔开：第一个人收到的饼干美味度。

第三行包含k kk个正整数，用一个空格隔开：第二个人收到的饼干美味度。

输出必须满足以下要求：

每个人至少收到一个饼干。
每个人收到饼干的总美味度相同。
你只能使用送达的饼干。
每个饼干只能分给至多一个人。

任何符合要求的输出都将被判为 AC。特别地，你可以以任意顺序输出选择的饼干。

在你输出完最后三行后，最后刷新一次输出流，并正常结束程序。

输入输出样例 #1

输入 #1

1 13 7 31 12 5 3

输出 #1

? 13 ? 7 ? 31 ? 12 ? 5 ? 3 ! 2 3 7 13 12 5 3

输入输出样例 #2

输入 #2

2 7 2 5

输出 #2

? 3 7 ? 2 8 ? 1 5 ! 2 1 2 5 7

说明/提示

提示

样例输入输出应该一行一行阅读。你的程序交替从标准输入读一个整数以及向标准输出打印一行（或最后三行）。

交互库任意地选择送达的饼干。这意味着在某些测试点中，交互库可能是自适应的；但在另一些测试点中，交互库可能随机选择。特别地，对于n = 2 n=2n=2，如果你跟样例2 22输出相同的订单，你可能得到不同的结果。

数据范围

对于全部数据，1 ≤ n ≤ 5 × 10 3 1\le n\le 5\times 10^31≤n≤5×103。

子任务一（8 88分）：n = 1 n=1n=1。
子任务二（9 99分）：n ≤ 2 n\le 2n≤2。
子任务三（18 1818分）：n ≤ 25 n\le 25n≤25。
子任务四（16 1616分）：n ≤ 200 n\le 200n≤200。
子任务五（13 1313分）：n ≤ 10 3 n\le 10^3n≤103。
子任务六（36 3636分）：无特殊限制。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#definelllonglongvector<ll>seletc;vector<ll>out;vector<array<ll,2>>oknum;ll n,pos,mv,ans,anspos;intmain(){cin>>n;pos=n+1;for(ll _=0;_<13;_++){cout<<'?';for(ll __=n;__>0;__--){cout<<' ';pos++;cout<<pos;}cout<<endl;ll tmp;cin>>tmp;seletc.push_back(tmp);pos<<=1;pos+=n;}oknum.push_back({0,0});for(ll i=0;i<13;i++)for(ll k=0;k<(1<<i);k++)oknum.push_back({oknum[k][0]+seletc[i],oknum[k][1]+(1<<i)});cout<<'?';for(ll i=1;i<=n;i++)cout<<' '<<i+(ll)(1e15);cout<<endl;cin>>mv;cout<<'?';for(ll i=1;i<=n;i++)cout<<' '<<mv+oknum[i][0];cout<<endl;cin>>ans;for(ll i=1;i<=n;i++)if(ans-mv==oknum[i][0])anspos=i;ll msk=oknum[anspos][1];for(ll k=0;k<13;k++){if(msk%2==1)out.push_back(seletc[k]);msk/=2;}cout<<"! 1 "<<out.size()+1<<endl<<ans<<endl<<mv;for(ll i:out){cout<<' '<<i;}cout<<endl;return0;}