oj.uz

Submission #420063

# Submission time Handle Problem Language Result Execution time Memory
420063 2021-06-08T04:40:46 Z oolimry Monster Game (JOI21_monster) C++17
100 / 100
 143 ms 1548 KB 
#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

map<ii, int> M;
bool query(int a, int b){
	if(M.find(ii(a,b)) != M.end()) return M[ii(a,b)];
	int res = Query(a,b);
	//show3(a,b,res);
	M[ii(a,b)] = res;
	M[ii(b,a)] = not res;
	return res;
}

struct thing{
	int s, e, c;
};

vector<int> Solve(int n) {
	vector<int> T(0);
	vector<int> A(n);
	vector<int> B(n);
	//for (int i = 0; i < n; i++) T[i] = i;
	for (int i = 0; i < n; i++) A[i] = 0;
	for (int i = 0; i < n; i++) B[i] = 0;
	int seed = time(0);
	//srand(1622964658);
	srand(1622968914);
	
	T.push_back(0);
	for(int i = 1;i < n;i++){
		int low = -1, high = sz(T);
		while(low != high-1){
			int mid = (low+high)/2;
			if(query(T[mid], i)) high = mid;
			else low = mid;
		} 
		T.insert(T.begin()+low+1, i);
		
	}
	
	//cerr << "------------" << endl;
	
	//cerr << "------------" << endl;
	int a = 0;
	bool awins = false;
	vector<thing> ranges;
	for(int i = 1;i < n;i++){
		if(i <= a+1) continue;
		//show2(a,i)
		if(i == a+2) awins = query(T[a], T[i]);
		else{
			if(awins){
				if(not query(T[a], T[i])){
					if(i-1 == a+2){
						ranges.push_back({a,i-1,2});
					}
					else{
						ranges.push_back({a,i-1,1});
					}
					a = i;
				}
			}
			else{
				if(query(T[a], T[i])){
					ranges.push_back({a,i,2});
					a = i+1;
				}
			}
		}
	}
	
	if(a != n) ranges.push_back({a,n-1,1});
	
	int zero = -1;
	if(ranges[0].e != 2){
		///solve range 0;
		int e = ranges[0].e;
		int x = e;
		
		int cnt = 0;
		int e2 = ranges[0].e;
		if(sz(ranges) > 1) e2 = ranges[1].e;
		
		for(int i = 0;i <= e2;i++){
			if(i == x) continue;
			if(query(T[x], T[i])) cnt++;
		}
		
		if(ranges[0].c == 2){
			if(cnt == 1) zero = 0;
			else zero = 1;
		}
		else{
			if(cnt == 1) zero = e;
			else zero = e-1;
		}
	}
	else{
		int x = 0;
		while(x < 2){
			int cnt = 0;
			int e2 = ranges[0].e;
			if(sz(ranges) > 1) e2 = ranges[1].e;
			
			for(int i = 0;i <= e2;i++){
				if(i == x) continue;
				if(query(T[x], T[i])) cnt++;
			}
			
			if(cnt != 1){
				break;
			}
			x++;
		}
		zero = (x+2)%3;
	}
	//show(zero);
	for(int i = 0;i <= ranges[0].e;i++){
		A[i] = T[(zero-i+ranges[0].e+1)%(ranges[0].e+1)];
	}
	
	for(int rno = 1;rno < sz(ranges);rno++){
		int s = ranges[rno].s; int e = ranges[rno].e;
		int z = s;
		int L = (e-s+1);
		for(int i = 0;i < L;i++){
			if(query(A[s-1],T[i+s])){
				z = i+s;
				break;
			}
			if(query(A[s-1],T[e-i])){
				z = e-i;
				break;
			}
		}
		//show(z);
		for(int i = 0;i < L;i++){
			A[i+s] = T[(z-i-s+L+L)%L+s];
		}
	}
	
	for(int i = 0;i < n;i++) B[A[i]] = i;
	//cerr << "------------" << endl;

	return B;
}

Compilation message

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:33:6: warning: unused variable 'seed' [-Wunused-variable]
   33 |  int seed = time(0);
      |      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 200 KB Output is correct
14 Correct 1 ms 200 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 17 ms 436 KB Output is correct
17 Correct 9 ms 444 KB Output is correct
18 Correct 17 ms 356 KB Output is correct
19 Correct 14 ms 428 KB Output is correct
20 Correct 15 ms 404 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 20 ms 448 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 14 ms 444 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 200 KB Output is correct
14 Correct 1 ms 200 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 17 ms 436 KB Output is correct
17 Correct 9 ms 444 KB Output is correct
18 Correct 17 ms 356 KB Output is correct
19 Correct 14 ms 428 KB Output is correct
20 Correct 15 ms 404 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 20 ms 448 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 14 ms 444 KB Output is correct
33 Correct 126 ms 1388 KB Output is correct
34 Correct 101 ms 1452 KB Output is correct
35 Correct 111 ms 1348 KB Output is correct
36 Correct 68 ms 1460 KB Output is correct
37 Correct 112 ms 1384 KB Output is correct
38 Correct 116 ms 1400 KB Output is correct
39 Correct 134 ms 1548 KB Output is correct
40 Correct 101 ms 1368 KB Output is correct
41 Correct 129 ms 1368 KB Output is correct
42 Correct 120 ms 1352 KB Output is correct
43 Correct 122 ms 1472 KB Output is correct
44 Correct 90 ms 1360 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1336 KB Output is correct
2 Correct 99 ms 1356 KB Output is correct
3 Correct 123 ms 1452 KB Output is correct
4 Correct 127 ms 1432 KB Output is correct
5 Correct 128 ms 1468 KB Output is correct
6 Correct 88 ms 1420 KB Output is correct
7 Correct 63 ms 1400 KB Output is correct
8 Correct 96 ms 1416 KB Output is correct
9 Correct 98 ms 1432 KB Output is correct
10 Correct 66 ms 1460 KB Output is correct
11 Correct 123 ms 1416 KB Output is correct
12 Correct 93 ms 1352 KB Output is correct
13 Correct 143 ms 1352 KB Output is correct
14 Correct 116 ms 1348 KB Output is correct
15 Correct 104 ms 1428 KB Output is correct
16 Correct 48 ms 1388 KB Output is correct
17 Correct 122 ms 1408 KB Output is correct
18 Correct 101 ms 1384 KB Output is correct