QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335100#8216. Jumbled Primesucup-team1209#AC ✓757ms3668kbC++204.1kb2024-02-22 17:24:352024-02-22 17:24:36

Judging History

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

  • [2024-02-22 17:24:36]
  • 评测
  • 测评结果:AC
  • 用时:757ms
  • 内存:3668kb
  • [2024-02-22 17:24:35]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 105;
int n = 100;
int cnt;
struct mm {
	private:
	int p[N];
	int is[N];
	int baseqry(int a, int b) {
		std::cout << "? " << a << ' ' << b << '\n';
		int res; cin >> res;
		return res;
		assert(a != b);
		++ cnt;
		return std::gcd(p[a], p[b]);
	}
	std::map<int, int> map;
	public:
	int qry(int a, int b) {
		if(a > b) std::swap(a, b);
		int z = a * n + b;
		auto iter = map.find(z);
		if(iter != map.end()) return iter -> second;
		return map[z] = baseqry(a, b);
	}
	void submit(int * ans) {
		cout << "! ";
		for(int i = 1;i <= n;++i) {
			cout << ans[i];
		}
		cout << '\n';
		return ;
		for(int i = 1;i <= n;++i) {
			if(ans[i] != is[p[i]]) {
				assert(ans[i] == is[p[i]]);
			}
		}
	}
	void init() {
		static std::mt19937 gen(20);
		map.clear();
		for(int i = 1;i <= n;++i) p[i] = i, is[i] = 1;
		for(int i = 2;i <= n;++i)
			for(int j = i + i;j <= n;j += i) is[j] = 0;
		std::shuffle(p + 1, p + n + 1, gen);
		std::shuffle(p + 1, p + n + 1, gen);
		std::shuffle(p + 1, p + n + 1, gen);
	}
} q;
int ans[N];
int main() {
	std::mt19937_64 gen(1);
	std::ios::sync_with_stdio(false);
	for(int i = 1;i <= 1000;++i) {
		q.init();
		int v[4] = {-1, -1, -1, -1};
		for(;v[1] == -1 || v[2] == -1 || v[3] == -1;) {
			int a = gen() % n + 1, b;
			do b = gen() % n + 1; while(a == b);
			int res = q.qry(a, b);
			if(res % 5 == 0) v[1] = a;
			if(res % 7 == 0) v[2] = a;
			if(res % 4 == 0) v[3] = a;
		}
		std::vector<int> p5 = {v[1]};
		std::vector<int> p7 = {v[2]};
		auto ins = [&](auto & v, int i, int p, int nd) {
			if(i == v[0]) return -1;
			int z = q.qry(v[0], i);
			if(z % p) return -1;
			if(z % nd == 0) return v[0];
			for(int j = 1;j < (int) v.size();++j) {
				if(q.qry(v[j], i) % nd == 0) return i;
			}
			v.push_back(i);
			return -1;
		};
		int v35 = -1;
		int v27 = -1;
		for(int i = 1;i <= n;++i) {
			if(v35 < 0) {
				int p = ins(p5, i, 5, 3);
				if(p > 0) v35 = p;
			}
			if(v27 < 0) {
				int p = ins(p7, i, 7, 2);
				if(p > 0) v27 = p;
			}
		}
		std::vector<int> vc[1 << 4];
		for(int i = 1;i <= n;++i) {
			int mask = 0;
			if(v27 == i) mask |= 9;
			else {
				int w = q.qry(v27, i);
				if(w % 2 == 0) mask |= 1;
				if(w % 7 == 0) mask |= 8;
			}
			if(v35 == i) mask |= 6;
			else {
				int w = q.qry(v35, i);
				if(w % 3 == 0) mask |= 2;
				if(w % 5 == 0) mask |= 4;
			}

			ans[i] = mask == 0;

			vc[mask].push_back(i);
		}
		auto solve0 = [&](std::vector<int> & v, std::vector<int> & pms, int pb = 1) {
			std::vector<int> res;
			for(int i : v) {
				int ok = 1;
				for(int id = 0;id < (int) pms.size();++id) {
					int & j = pms[id];
					if((pb || j > 0) && q.qry(i, std::abs(j)) > 1) {
						if(j > 0) j *= -1;
						ok = 0;
						break;
					}
				}
				if(ok) res.push_back(i);
			}
			v = res;
		};
		auto solve1 = [&](std::vector<int> & v, int p) {
			for(int j = 0;j < (int) v.size();++j) {
				int ok = 1;
				for(int k : v) {
					if(v[j] == k) continue;
					if(q.qry(v[j], k) != p) {
						ok = 0;
						break;
					}
				}
				if(ok) {
					ans[v[j]] = 1;
					break;
				}
			}
		};
		auto solve2 = [&](std::vector<int> & v, int p) {
			int mk = 1 | (p == 5 ? 4 : 8);
			int yes = 1, pb = v[0];
			for(int j : vc[mk]) {
				int ans = q.qry(pb, j);
				if(ans > p) {
					yes = 0;
					break;
				}
			}
			ans[yes ? v[0] : v[1]] = 1;
		};
		vc[1].erase(remove_if(vc[1].begin(), vc[1].end(), [&](int x) {
			return x == v[3] || q.qry(x, v[3]) % 4 == 0;
		}), vc[1].end());
		solve0(vc[1], vc[0], 0);

		std::vector<int> p;
		for(int x : vc[0]) if(x < 0) p.push_back(-x);
		vc[0] = p;

		solve0(vc[2], vc[0]), p = {};
		for(int x : vc[0]) if(x < 0) p.push_back(-x);
		vc[0] = p;

		solve0(vc[4], vc[0]), p = {};
		for(int x : vc[0]) if(x < 0) p.push_back(-x);
		vc[0] = p;

		solve0(vc[8], vc[0]), p = {};
		for(int x : vc[0]) if(x < 0) p.push_back(-x);
		vc[0] = p;


		solve1(vc[1], 2);
		solve1(vc[2], 3);

		solve2(vc[4], 5);
		solve2(vc[8], 7);


		q.submit(ans);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 757ms
memory: 3668kb

input:

1
3
1
1
2
2
1
1
2
3
1
1
1
1
3
1
1
3
1
1
1
2
1
2
1
13
1
2
1
2
2
1
1
1
1
6
1
1
1
4
25
4
1
1
2
1
1
3
6
1
1
1
1
1
1
2
1
1
2
4
1
5
1
1
1
1
1
1
1
1
1
3
1
3
1
3
1
9
7
1
1
1
7
1
1
25
5
1
1
2
1
50
25
5
1
1
1
1
5
5
5
5
2
1
4
1
10
5
10
5
5
1
1
2
7
7
1
1
4
1
5
4
1
4
1
20
5
10
5
30
5
1
1
5
1
1
1
1
1
1
1
5
1
1
5
...

output:

? 29 63
? 31 47
? 10 85
? 29 66
? 25 49
? 64 77
? 8 78
? 34 81
? 11 70
? 1 24
? 68 84
? 68 89
? 28 95
? 40 78
? 1 31
? 4 66
? 29 38
? 5 47
? 55 92
? 21 30
? 29 85
? 25 58
? 27 100
? 20 100
? 23 91
? 32 89
? 18 33
? 15 48
? 36 52
? 58 59
? 12 88
? 9 49
? 14 100
? 60 90
? 11 23
? 53 93
? 36 75
? 40 60...

result:

ok Primes are found successfully with S = 577423 queries total