QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490122#8819. CNOI Knowledgedaishuchen2010WA 1ms3560kbC++201.1kb2024-07-25 11:27:242024-07-25 11:27:24

Judging History

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

  • [2024-07-25 11:27:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3560kb
  • [2024-07-25 11:27:24]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3560kb

input:

12
3
3
6
6
10
6
3
1
10
3
1
10
3
1
14
6
3
1
14
6
3
1
19
5
2
19
5
3
1
25
9
3
1

output:

? 1 2
? 2 3
? 1 3
? 2 4
? 1 4
? 3 5
? 4 5
? 5 5
? 3 6
? 5 6
? 6 6
? 4 7
? 6 7
? 7 7
? 4 8
? 6 8
? 7 8
? 8 8
? 5 9
? 7 9
? 8 9
? 9 9
? 5 10
? 8 10
? 9 10
? 6 11
? 9 11
? 10 11
? 11 11
? 6 12
? 9 12
? 11 12
? 12 12
! 1 2 3 4 4 4 4 4 4 4 4 4 

result:

wrong answer Wrong Answer.