oj.uz

Submission #811186

# Submission time Handle Problem Language Result Execution time Memory
811186 2023-08-07T02:06:59 Z maomao90 Ancient Machine 2 (JOI23_ancient2) C++17
37 / 100
 1461 ms 496 KB 
#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 500005;

namespace {
	int n;
	char findPrefix(int p) {
		int m = p + 3;
		vi a(m);
		iota(ALL(a), 1);
		a[p + 1] = p + 1;
		a[p + 2] = p + 2;
		vi b = a;
		a[p] = p + 1;
		b[p] = p + 2;
		int r = Query(m, a, b);
		return '0' + (r == p + 2);
	}
	char findSuffix(string s) {
		s = "1" + s;
		int n = SZ(s);
		s += "?";
		int m = n + 1;
		vi a(m), b(m);
		string ps = "";
		REP (i, 0, n + 1) {
			auto get = [&] (char c) {
				string ts = ps + c;
				REP (j, 0, SZ(ts)) {
					bool pos = 1;
					REP (k, 0, SZ(ts) - j) {
						if (ts[j + k] != s[k]) {
							pos = 0;
						}
					}
					if (pos) {
						return SZ(ts) - j;
					}
				}
				return 0;
			};
			a[i] = get('0');
			b[i] = get('1');
			ps += s[i];
		}
		int r = Query(m, a, b);
		return '0' + (r == m - 1);
	}
}

string Solve(int N) {
	n = N;
	string ans(n, '0');
	REP (i, 0, n / 2) {
		ans[i] = findPrefix(i);
	}
	string suf = "";
	RREP (i, n - 1, n / 2) {
		ans[i] = findSuffix(suf);
		suf = ans[i] + suf;
	}
	cerr << ans << '\n';
	return ans;
}

Subtask #1
37.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1331 ms 336 KB Output is partially correct
2 Partially correct 1326 ms 336 KB Output is partially correct
3 Partially correct 1354 ms 336 KB Output is partially correct
4 Partially correct 1350 ms 420 KB Output is partially correct
5 Partially correct 1325 ms 336 KB Output is partially correct
6 Partially correct 1331 ms 364 KB Output is partially correct
7 Partially correct 1359 ms 420 KB Output is partially correct
8 Partially correct 1316 ms 336 KB Output is partially correct
9 Partially correct 1357 ms 396 KB Output is partially correct
10 Partially correct 1348 ms 344 KB Output is partially correct
11 Partially correct 1238 ms 452 KB Output is partially correct
12 Partially correct 1364 ms 352 KB Output is partially correct
13 Partially correct 1230 ms 336 KB Output is partially correct
14 Partially correct 1351 ms 400 KB Output is partially correct
15 Partially correct 1347 ms 336 KB Output is partially correct
16 Partially correct 1357 ms 396 KB Output is partially correct
17 Partially correct 1360 ms 336 KB Output is partially correct
18 Partially correct 1361 ms 320 KB Output is partially correct
19 Partially correct 1384 ms 328 KB Output is partially correct
20 Partially correct 1417 ms 416 KB Output is partially correct
21 Partially correct 1371 ms 416 KB Output is partially correct
22 Partially correct 1341 ms 496 KB Output is partially correct
23 Partially correct 1299 ms 336 KB Output is partially correct
24 Partially correct 1352 ms 420 KB Output is partially correct
25 Partially correct 1349 ms 420 KB Output is partially correct
26 Partially correct 1372 ms 336 KB Output is partially correct
27 Partially correct 1324 ms 428 KB Output is partially correct
28 Partially correct 1341 ms 336 KB Output is partially correct
29 Partially correct 1341 ms 416 KB Output is partially correct
30 Partially correct 1334 ms 336 KB Output is partially correct
31 Partially correct 1275 ms 336 KB Output is partially correct
32 Partially correct 1317 ms 420 KB Output is partially correct
33 Partially correct 1332 ms 324 KB Output is partially correct
34 Partially correct 1342 ms 436 KB Output is partially correct
35 Partially correct 1333 ms 420 KB Output is partially correct
36 Partially correct 1333 ms 416 KB Output is partially correct
37 Partially correct 1336 ms 416 KB Output is partially correct
38 Partially correct 1311 ms 420 KB Output is partially correct
39 Partially correct 1237 ms 336 KB Output is partially correct
40 Partially correct 1341 ms 428 KB Output is partially correct
41 Partially correct 1337 ms 336 KB Output is partially correct
42 Partially correct 1364 ms 336 KB Output is partially correct
43 Partially correct 1290 ms 420 KB Output is partially correct
44 Partially correct 1299 ms 336 KB Output is partially correct
45 Partially correct 1385 ms 404 KB Output is partially correct
46 Partially correct 1321 ms 436 KB Output is partially correct
47 Partially correct 1377 ms 336 KB Output is partially correct
48 Partially correct 1341 ms 404 KB Output is partially correct
49 Partially correct 1389 ms 376 KB Output is partially correct
50 Partially correct 1321 ms 396 KB Output is partially correct
51 Partially correct 1372 ms 440 KB Output is partially correct
52 Partially correct 1307 ms 336 KB Output is partially correct
53 Partially correct 1328 ms 336 KB Output is partially correct
54 Partially correct 1345 ms 340 KB Output is partially correct
55 Partially correct 1461 ms 428 KB Output is partially correct
56 Partially correct 1384 ms 420 KB Output is partially correct
57 Partially correct 1296 ms 456 KB Output is partially correct
58 Partially correct 1314 ms 424 KB Output is partially correct
59 Partially correct 1323 ms 336 KB Output is partially correct
60 Partially correct 1338 ms 420 KB Output is partially correct
61 Partially correct 1247 ms 432 KB Output is partially correct
62 Partially correct 1260 ms 420 KB Output is partially correct
63 Partially correct 1377 ms 416 KB Output is partially correct