QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489302#8819. CNOI KnowledgeYansuan_HClRE 0ms0kbC++142.5kb2024-07-24 19:22:542024-07-24 19:22:54

Judging History

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

  • [2024-07-24 19:22:54]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-24 19:22:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define U(i,l,r) for (int i(l),END##i(r); i<=END##i; ++i)
#define D(i,l,r) for (int i(l),END##i(r); i>=END##i; --i)
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline))
#define vc vector
#define ar array
#define pb push_back
#define eb emplace_back
#define el '\n'
using ll = long long;

const int N = 1003;
int n; int dist[N][N]; int s[N];
// 子串对应从 everything 到终结点的路径

// struct sam {
// 	map<int, int> ch;
// 	int tag, link, len;
// } tr[N * 2]; int ptr, last;
// void init() { ptr = 0; tr[0].link = -1; last = 0; }
// void append(int c) {
// 	int p = ++ptr; tr[p].len = tr[last].len + 1;
// 	int u = last; last = p;
// 	while (u != -1 && !tr[u].ch[c]) {
// 		tr[u].ch[c] = p;
// 		u = tr[u].link;
// 	}
// 	if (u != -1) {
// 		int q = tr[u].ch[c];
// 		if (tr[q].len == tr[u].len + 1) tr[p].link = q;
// 		else {
// 			int r = ++ptr; tr[r] = tr[q]; tr[r].tag = 0; tr[r].len = tr[u].len + 1;
// 			tr[q].link = tr[p].link = r;
// 			while (u != -1 && tr[u].ch[c] == q) {
// 				tr[u].ch[c] = r;
// 				u = tr[u].link;
// 			}
// 		}
// 	}

const ll P = 998244353, BA = 114514;
ll pb[N];
ll hsh[N];
ll f[N][N];
map<pair<ll, int>, int> last;

void insert(int p, int c) {
	hsh[p] = hsh[p - 1] * BA + c;
	f[p][p] = 1;
	int delta = 0, d[N] {};
	D (i, p, 1) {
		ll h = ((hsh[p] - hsh[i - 1] * pb[p - i + 1]) % P + P) % P;
		int j = last[{h, p - i + 1}];
		if (j) {
			U (k, 0, p - i)
				assert(s[j + k] == s[i + k]);
		}
		assert(j < i);
		++d[j]; last[{h, p - i + 1}] = i;
	}
	set<pair<ll, int>> tmp;
	D (i, p - 1, 1) {
		delta += d[i];
		f[i][p] = f[i][p - 1] + (p - i + 1) - delta;

		int l = i, r = p;
		ll h = hsh[r] - hsh[l - 1] * pb[r - l + 1];
		h = (h % P + P) % P;
		tmp.emplace(h, r - l + 1);
		assert((p - i + 1) - delta == tmp.size());
	}
}

int ask(int l, int r) {
	cout << "? " << l << ' ' << r << endl;
	int v; cin >> v;
	return v;
}
int main() {
	pb[0] = 1; U (i, 1, N - 1) pb[i] = pb[i - 1] * BA % P;
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);

	cin >> n;
	s[1] = 1;
	insert(1, 1);
	int p = 1;
	U (i, 2, n) {
		int l = 0, r = i - 1;
		while (l < r) {
			int mid((l + r + 1) >> 1), cur = ask(mid, i);
			if (cur == f[mid][i - 1] + (i - mid + 1))
				r = mid - 1;
			else
				l = mid;
		}
		if (l) s[i] = s[l];
		else s[i] = ++p;
		insert(i, s[i]);
	}
	cout << "!";
	U (i, 1, n)
		cout << ' ' << s[i];
	cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

12
3

output:

? 1 2

result: