CF1764G3 Doremy‘s Perfect DS Class (Hard/Medium/Easy Version) 二分

Doremy’s Perfect DS Class (Hard/Medium/Easy Version)

传送门Easy

传送门Medium

传送门Hard

题面翻译

• 这是一道交互题。
• 交互库有一个 $[1,n]$ 的排列 $p$。
• 你可以询问 $l,r,k$，交互库会返回 $?\frac{p_l}{k}?,?\frac{p_{l+1}}{k}?,?,?\frac{p_r}{k}?$ 中不同数的个数。
• 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。
• $n\in [3,1024]$。

题目描述

The only difference between this problem and the other two versions is the maximum number of queries. In this version, you are allowed to ask at most $ \mathbf{20} $ queries. You can make hacks only if all versions of the problem are solved.

This is an interactive problem.

“Everybody! Doremy’s Perfect Data Structure Class is about to start! Come and do your best if you want to have as much IQ as me!” In today’s Data Structure class, Doremy is teaching everyone a powerful data structure — Doremy tree! Now she gives you a quiz to prove that you are paying attention in class.

Given an array $a$ of length $m$ , Doremy tree supports the query $Q(l,r,k)$ , where $1\le l\le r\le m$ and $1\le k\le m$ , which returns the number of distinct integers in the array $\left[?\frac{a_l}{k}?,?\frac{a_{l+1}}{k}?,\dots ,?\frac{a_r}{k}?\right]$ .

Doremy has a secret permutation $p$ of integers from $1$ to $n$ . You can make queries, in one query, you give $3$ integers $l,r,k$ ( $1\le l\le r\le n$ , $1\le k\le n$ ) and receive the value of $Q(l,r,k)$ for the array $p$ . Can you find the index $y$ ( $1\le y\le n$ ) such that $p_y=1$ in at most $20$ queries?

Note that the permutation $p$ is fixed before any queries are made.

输入格式

输出格式

You begin the interaction by reading an integer $n$ ( $3\le n\le 1024$ ) in the first line — the length of the permutation.

To make a query, you should output

• "? $lrk$ " ( $1\le l\le r\le n$ , $1\le k\le n$ )

in a separate line. After each query, you should read an integer $x$ — the value of $Q(l,r,k)$ for $p$ . In this version of the problem, you can make at most $20$ such queries.To give the answer, you should output

• "! $y$ " ( $1\le y\le n$ )

in a separate line, where $p_y=1$ .After printing a query or the answer, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks Format

The first line of the hack contains an integer $n$ ( $3\le n\le 1024$ ) — the length of the permutation.

The second line of the hack contains $n$ distinct integers $p_1,p_2,\dots ,p_n$ ( $1\le p_i\le n$ ) — the permutation.

样例 #1

样例输入 #1

5

2

2

1

3

样例输出 #1

? 1 3 4

? 3 5 3

? 3 4 5

? 3 5 2

! 4

提示

The permutation in the example is $[3,5,2,1,4]$ .

The input and output for example illustrate possible interaction on that test (empty lines are inserted only for clarity).

In this interaction process:

• For the first query, $?\frac{3}{4}?=0,?\frac{5}{4}?=1,?\frac{2}{4}?=0$ , so the answer is $2$ .
• For the second query, $?\frac{2}{3}?=0,?\frac{1}{3}?=0,?\frac{4}{3}?=1$ , so the answer is still $2$ .
• For the third query, $?\frac{2}{5}?=0,?\frac{1}{5}?=0$ , so the answer is $1$ .
• For the fourth query, $?\frac{2}{2}?=1,?\frac{1}{2}?=0,?\frac{4}{2}?=2$ , so the answer is $3$ .

The correct answer is got after $4$ queries, so this process will be judged correct.

解题思路

阅读须知

• 请确保你有 $60$ min以上的时间来阅读此题解。
• 请确保你有足够好的记忆。
• 阅读时请保持高度专心状态。

Easy

考虑 $1$ 和其他的数有什么不同点。我们令询问的 $k=2$，那么只有 $1$ 的值是 $0$，其余都不是。这看起来并没有什么用，因为我们只能知道不同的数的个数。
可以发现，若 $k=2$，则所有数下取整后是两两配对的，$?\frac{2}{2}?=?\frac{3}{2}?,?\frac{4}{2}?=?\frac{5}{2}?\dots$。当 $n$ 为奇数时，只有 $1$ 是单出来的；$n$ 为偶数时，$1$ 和 $n$ 两个数都是单出来的。 于是就可以分类讨论：

$n$ 为奇数：

对于一个区间 $[l,r]$，若 $\mathrm{query}(l,r,2)=x$，可以得到 $[l,r]$ 中有 $2x?(r?l+1)$ 个数字没有被配对。所以假设我们找了一个分界点 $mid$，并求出 $[1,mid]$ 中有 $L$ 个没配对，$[mid+1,n]$ 中有 $R$ 个没配对。那么如果同一组的数分到了一边一个，它们可以互相消掉，只有 1 是无论如何都无法被配对的。
这就是说，若 $L<R$，$1$ 就在 $[mid+1,n]$ 中；否则 $1$ 在 $[1,mid]$ 中。那么我们可以二分这个 $mid$ 的位置，求出答案，询问次数 $2\times \log n\le 20$。

$n$ 为奇数：

我们同样询问得到 $L$ 和 $R$ 的值。分类讨论 $1$ 和 $n$ 的位置情况：

• 如果都在左侧，应该是 $L=R+2$；
• 如果都在右侧，应该是 $R=L+2$；
• 如果一左一右，$L=R$。

在一左一右的情况下，我们看似没法判断哪一边是 $1$，其实可以找出 $n$ 的位置：令 $k=n$，这样只有 $n$ 的答案是 $1$，其他都是 $0$。因此可以在一开始先二分找出 $n$ 的位置，就能知道 $L=R$ 时 $1$ 在哪边了。
找 $n$ 的位置只需要询问一边，所以总询问次数是 $3\times \log n\le 30$。

Medium

发现找 $1$ 的位置的过程是不好优化的，现在的询问次数难点在找 $n$ 的位置。
实际上，我们只关心 $n$ 在 $mid$ 的哪一侧，而不关心它的具体位置。可以这样优化：

• 当第一次出现 $L=R$ 的情况时，我们通过一次 $\mathrm{query}(1,mid,n)$ 判断 $n$ 在 $mid$ 的哪一侧。
• 当再次出现这个情况时，发现有一条性质：如果之前判断过 $n$ 在 $mid$ 的右侧，我们的二分区间只会往左不会往右，也就是说以后 $n$ 永远在 $mid$ 的右侧，反之同理。

因此，在第一次判断时记录 $n$ 在 $mid$ 的哪一侧，以后不需要再次判断。总询问次数为 $2\times \log n+1\le 21$。

Hard

还需要再卡掉一次询问，使询问次数到 $20$ 以内。
考虑二分的终止状态，在 $l+1=r$ 的情况下，把两边都问一遍看起来就不太划算，可以只问一边呢。

S1

如果我们现在还没询问过 $n$ 在 $mid$ 的哪一侧，说明 $n$ 还在区间 $[l,r]$ 中。换句话讲，$l$ 和 $r$ 的位置上一个是 $n$ 一个是 $1$。
这种情况简单的：一次询问就能找出 $n$ 的位置，剩下的那个自然是 $1$。

S2

$n$ 不在区间里，考虑我们已经知道了哪些信息。
在达成当前局面之前，我们曾令 $mid=l?1$，也曾令 $mid=r$。所以可以知道 $\mathrm{query}(1,l?1,2)$ 和 $\mathrm{query}(r+1,n,2)$ 的答案。于是就有了如下操作：

• 设 $[1,l?1]$ 未配对的个数为 $[r+1,n]$ 为 $R$。因为已经知道 $n$ 在哪一侧，可以在这步直接减掉 $n$ 的贡献。
• 若 $L<R$，表明 $[l,r]$ 中剩余的两个数，除了 $1$ 以外的那个是跟 $[1,l?1]$ 中的某个数配对的。因此我们询问 $[1,l]$ 中未配对的个数为 $L^{\prime }$ ，若 $L^{\prime }<L$，说明这个数与左边配对成功了，$1$ 在 $r$ 位置上；否则说明配对失败了，$1$ 在 $l$ 位置。
• $L>R$ 情况同上操作，稍加改动。

在完成该操作后，最后一步二分被优化到一次询问，询问次数上界为 $2\times \log n\le 20$，$Hard$ 版成功解决。

$$至此，艺术已成。$$

AC Code（适用easy/medium/hard）

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <Licenses - GNU Project - Free Software Foundation>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
	#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
	#include <ccomplex>
	#include <cfenv>
	#include <cinttypes>
	#include <cstdalign>
	#include <cstdbool>
	#include <cstdint>
	#include <ctgmath>
	#include <cwchar>
	#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
	#include <array>
	#include <atomic>
	#include <chrono>
	#include <condition_variable>
	#include <forward_list>
	#include <future>
	#include <initializer_list>
	#include <mutex>
	#include <random>
	#include <ratio>
	#include <regex>
	#include <scoped_allocator>
	#include <system_error>
	#include <thread>
	#include <tuple>
	#include <typeindex>
	#include <type_traits>
	#include <unordered_map>
	#include <unordered_set>
#endif
using namespace std;
#define int long long
int n;
map<pair<int, int>, int> Map;
int answer;
inline int Ask(int l, int r, int p) {
	if (Map.count({l, r}) && p == 2) {
		return Map[ {l, r}];
	}
	int x;
	if (l == r) {
		x = 1;
	} else if (l == 1 && r == n) {
		x = n / p + 1;
	} else {
		cout << "? " << l << " " << r << " " << p << endl;
		cin >> x;
	}
	if (p == 2) {
		Map[ {l, r}] = x;
	}
	return x;
}
inline int choose_project(int n) {
	return n & 1 ? 1 : 2;
}
inline int binery_sreach_to_project_1() {
	int answer;
	int l, r, mid;
	l = 1, r = n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (mid == n) {
			answer = n;
			break;
		}
		int val_l = Ask(1, mid, 2);
		val_l = 2 * val_l - mid;
		int val_r = Ask(mid + 1, n, 2);
		val_r = 2 * val_r - (n - mid);
		if (val_l < val_r) {
			l = mid + 1;
		} else {
			r = mid - 1;
			answer = mid;
		}
	}
	return answer;
}
inline int binery_sreach_to_project_2() {
	int answer;
	int l, r, mid;
	l = 1, r = n;
	int tmp = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (mid == n) {
			answer = n;
			break;
		}
		if (l == r && l != 1) {
			if (tmp == -1) {
				if (Ask(1, l, n) == 1) {
					answer = mid;
				}
				break;
			}
			int val1 = Ask(l, n, 2), val2 = Ask(l + 2, n, 2);
			if (val1 - val2 == 0) {
				break;
			} else if (val1 - val2 == 1) {
				if (Ask(1, l + 1, 2) - Ask(1, l - 1, 2) == 2 && Ask(l + 1, n, 2) == Ask(l + 2, n, 2)) {
					answer = mid;
				}
			} else {
				if (Ask(1, l - 1, 2) != Ask(1, l, 2)) {
					answer = mid;
				}
			}
			break;
		}
		int val_l = Ask(1, mid, 2);
		val_l = 2 * val_l - mid - (1 <= tmp && tmp <= mid);
		int val_r = Ask(mid + 1, n, 2);
		val_r = 2 * val_r - (n - mid) - (mid + 1 <= tmp && tmp <= n);
		if (val_l > val_r) {
			r = mid - 1;
			answer = mid;
		} else if (val_l < val_r) {
			l = mid + 1;
		} else {
			if (mid == 1) {
				if (Ask(mid + 1, n, n) == 2) {
					tmp = mid + 1;
					answer = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
					tmp = 1;
				}
			} else {
				if (Ask(1, mid, n) == 2) {
					l = mid + 1;
					tmp = 1;
				} else {
					answer = mid;
					tmp = mid + 1;
					r = mid - 1;
				}
			}
		}
	}
	return answer;
}
inline void work() {
	int projectnum;
	cin >> n;
	projectnum = choose_project(n);
	if (projectnum == 1) {
		answer = binery_sreach_to_project_1();
	} else if (projectnum == 2) {
		answer = binery_sreach_to_project_2();
	}
	cout << "! " << answer;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}