QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#490119#8819. CNOI Knowledgedaishuchen2010TL 0ms0kbC++201.1kb2024-07-25 11:25:292024-07-25 11:25:29

Judging History

你现在查看的是最新测评结果

  • [2024-07-25 11:25:29]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-25 11:25:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
const unsigned long long p = 322771;
int ans[MAXN],ts,cnt[MAXN],add[MAXN];
map <unsigned long long,int> mp;//表示最后一个哈希为x的字串的结尾
inline int ask(int l,int r)
{
	int res;
	cout << "? " << l << ' ' << r << '\n';
	cin >> res;
	return res;
}
inline int getid(int l,int r)
{
	int rr = r,mid;
	while (l <= r)
	{
		mid = (l + r) / 2;
		if (ask(mid,rr) - cnt[mid] == rr - mid + 1) r = mid - 1;
		else l = mid + 1;
	}
	return r;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,id;
	unsigned long long _h;
	cin >> n;
	cnt[1] = ans[1] = mp[1] = ts = 1;
	for (int i = 2; i <= n; i++)
	{
		_h = 0;
		id = getid(1,i);
		if (!id) ans[i] = ++ts;
		else ans[i] = ans[id];
		for (int j = 1; j < i; j++) add[j] = 0;
		for (int j = i; j >= 1; j--)
		{
			_h *= p,_h += ans[j];
			add[mp[_h] + 1]++,add[j + 1]--;//差分
			mp[_h] = j;
		}
		for (int j = 1; j <= i; j++) add[j] += add[j - 1],cnt[j] += add[j];
	}
	cout << "! ";
	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
	return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

12

output:


result: