oj.uz

Submission #420754

# Submission time Handle Problem Language Result Execution time Memory
420754 2021-06-08T13:44:22 Z egorlifar Monster Game (JOI21_monster) C++17
0 / 100
 2000 ms 288 KB 
/*
KAMUI!
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓██████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓▓█████▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓███▓▒▒░▒▒▒▒▒░░░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓█▓▒▒▒▓▓████████▓▒▒░▒▒▒▓██▓▓▓▓▓▓
▓▓▓▓██▒▓████████████████▓░▒▒▒▒▓██▓▓▓▓ 
▓▓▓██▓███████▓▒░░░░░░░▒███▒░░▒▒▒██▓▓▓ 
▓▓█████████▓░░░░░░░░░░░░░██▓▓██████▓▓ 
▓▓█▒▓███████████▓▓▒▒▒▓▓██████████▓█▓▓ 
▓██▒▒▒███████████████████████████▓▓█▓ 
▓█▓▒▒░░████████▒░░░░▓███████████▓░▒█▓ 
▓█▒▒▒░██░▒████░░░░░░█████░░████▓░░▒█▓ 
▓█▒▒▒▒██░░░██▓░░░░░░░███▒░░████▒▒▒▒█▓ 
▓█▓▒▒▒██▒░░░▓█▓░░░░░▓█▓░░░▓███▓▒▒░▓█▓ 
▓█▓▒▒▒███░░░░████████▓░░░░░████▒▒▒▓█▓ 
▓▓█▒▒░▓███░░░▒███████▒░░░▒███▓▒▒▒▒█▓▓ 
▓▓██▒▒░████▒░░███████░░░▓███▓░▒▒▒██▓▓ 
▓▓▓██▒▒▒█████▓░░██████▒▓███▓▒░▒▒██▓▓▓ 
▓▓▓▓██▓▒░▓██████████████▓▒░▒▒▒▓██▓▓▓▓ 
▓▓▓▓▓▓██▓░▒▓█████████▒░░▒▒▒▒▓██▓▓▓▓▓▓ 
▓▓▓▓▓▓▓███▓▒▒▓██████▓░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓███▓▓▓▓███▓▓▓████▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓███████████▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
*/
#include "monster.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 


mt19937 as;


vector<int> mysort(vector<int> cur) {
	if (sz(cur) <= 1) {
		return cur;
	}
	if (sz(cur) <= 8) {
		vector<int> sum(sz(cur)); 
	  	vector<pair<int, int> > st;
	  	for (int i = 0; i < sz(cur); i++) {
	  		for (int j = i + 1; j < sz(cur); j++) {
				int f = Query(cur[i], cur[j]);
				sum[i] += f;
	  			sum[j] += 1 - f;
	  		}
	  		st.pb(mp(sum[i], cur[i]));
	  	}
	  	sort(all(st));
	  	for (int i = sz(cur) - 2; i >= sz(cur) - 2; i--) {
	  		if (st[i].first == st[i + 1].first) {
	  			if (!Query(st[i + 1].second, st[i - 1].second) || !Query(st[i + 1].second, st[i - 2].second)) {
	  				swap(st[i], st[i + 1]);
	  			}
	  		}
	  	}
	  	for (int i = 0; i < 1; i++) {
	  		if (st[i].first == st[i + 1].first) {
	  			if (!Query(st[i + 1].second, st[i + 2].second)) {
	  				swap(st[i], st[i + 1]);
	  			}
	  		}
	  	}
	  	vector<int> res;
	  	for (auto x: st) {
	  		res.pb(x.second);
	  	}
	  	return res;
	}	 
	int f;
	vector<int> la, lb;
	while (true) {
		la.clear();
		lb.clear();
		f = cur[as() % sz(cur)];
		for (int i = 0; i < sz(cur); i++) {
			if (cur[i] != f) {
				if (Query(f, cur[i])) {
					la.pb(f);
				} else {
					lb.pb(f);
				}
			}
		}
		if (sz(la) >= 4 && sz(lb) >= 4) {
			break;
		}
	}
	la = mysort(la);
	lb = mysort(lb);
	vector<int> st;
	for (int i = 0; i < sz(la) - 1; i++) {
		st.pb(la[i]);
	}
	st.pb(lb[0]);
	st.pb(f);
	st.pb(la.back());
	for (int i = 1; i < sz(lb); i++)  {
		st.pb(lb[i]);
	}
	return st;
}

vector<int> Solve(int N) {
	as.seed(228);
  	vector<int> T(N);
  	vector<int> order;
  	for (int i = 0; i < N; i++) {
  		order.pb(i);
  	}
  	auto f = mysort(order);
  	for (int i = 0; i < N; i++) {
  		T[f[i]] = i;
  	}
  	return T;
}

Subtask #1
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 200 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 Execution timed out 3095 ms 200 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
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 200 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 Execution timed out 3095 ms 200 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 288 KB Time limit exceeded
2 Halted 0 ms 0 KB -