Submission #1001134

#TimeUsernameProblemLanguageResultExecution timeMemory
1001134shmaxJousting tournament (IOI12_tournament)C++17
17 / 100
1094 ms9816 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2,fma") //#pragma GCC optimization ("unroll-loops") //#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt") using namespace std; using namespace __gnu_pbds; #define int long long #define float long double #define elif else if #define endl "\n" #define mod 1000000007 #define pi acos(-1) #define eps 0.000000001 #define inf 1000'000'000'000'000'000LL #define FIXED(a) cout << fixed << setprecision(a) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define time_init auto start = std::chrono::high_resolution_clock::now() #define time_report \ auto end = std::chrono::high_resolution_clock::now(); \ std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl #define debug(x) \ { cerr << #x << " = " << x << endl; } #define len(x) (int) x.size() #define sqr(x) ((x) * (x)) #define cube(x) ((x) * (x) * (x)) #define bit(x, i) (((x) >> (i)) & 1) #define set_bit(x, i) ((x) | (1LL << (i))) #define clear_bit(x, i) ((x) & (~(1LL << (i)))) #define toggle_bit(x, i) ((x) ^ (1LL << (i))) #define low_bit(x) ((x) & (-(x))) #define count_bit(x) __builtin_popcountll(x) #define srt(x) sort(all(x)) #define rsrt(x) sort(rall(x)) #define mp make_pair #define maxel(x) (*max_element(all(x))) #define minel(x) (*min_element(all(x))) #define maxelpos(x) (max_element(all(x)) - x.begin()) #define minelpos(x) (min_element(all(x)) - x.begin()) #define sum(x) (accumulate(all(x), 0LL)) #define product(x) (accumulate(all(x), 1LL, multiplies<int>())) #define gcd __gcd #define lcm(a, b) ((a) / gcd(a, b) * (b)) #define rev(x) (reverse(all(x))) #define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end())) #define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend())) #define is_sorted(x) (is_sorted_until(all(x)) == x.end()) #define is_even(x) (((x) &1) == 0) #define is_odd(x) (((x) &1) == 1) #define pow2(x) (1LL << (x)) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; template<typename T> using max_heap = priority_queue<T, vector<T>, less<T>>; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using matrix = vector<vector<T>>; template<typename T> using graph = vector<vector<T>>; using hashmap = gp_hash_table<int, int, custom_hash>; template<typename T> vector<T> vect(int n, T val) { return vector<T>(n, val); } template<typename T> vector<vector<T>> vect(int n, int m, T val) { return vector<vector<T>>(n, vector<T>(m, val)); } template<typename T> vector<vector<vector<T>>> vect(int n, int m, int k, T val) { return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val))); } template<typename T> vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) { return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val)))); } template<typename T> matrix<T> new_matrix(int n, int m, T val) { return matrix<T>(n, vector<T>(m, val)); } template<typename T> graph<T> new_graph(int n) { return graph<T>(n); } template<class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template<class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t; template<typename T> using vec = vector<T>; using pII = pair<int, int>; template<typename T> using enumerated = pair<T, int>; template<typename it> struct SparseTable { using T = typename remove_reference<decltype(*declval<it>())>::type; vector<vector<T>> t; function<T(T, T)> f; vector<int> log; SparseTable() = default; SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) { int n = distance(first, last); t.assign(32 - __builtin_clz(n), vector<T>(n)); t[0].assign(first, last); // calc log log.resize(n + 1); for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1; for (int i = 1; i < t.size(); i++) for (int j = 0; j < n - (1 << i) + 1; j++) t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]); } // returns f(a[l..r]) in O(1) time T get(int l, int r) { int h = log[r - l + 1]; return f(t[h][l], t[h][r - (1 << h) + 1]); } }; int solve(int n, int c, int R, const vec<int> &k, vec<pair<int, int>> segs) { vec<int> t(n, 2); auto disable = [&](int l, int r) { for (int i = l; i <= r; i++) { t[i] = 0; } t[l] = 1; t[r] = 1; }; auto findk = [&](int id) { if (id == -1) return -1LL; for (int i = 0; i < n; i++) { id -= t[i]; if (id <= 0) { return i; } } return n; }; for (int i = 0; i < c; i++) { int f = findk(segs[i].first * 2 +1); int s = findk(segs[i].second * 2+2); segs[i] = {f, s}; disable(f, s); } int best = 0; int id = 0; for (int i = 0; i < n; i++) { vec<int> cur(n, -1); cur[i] = R; int ptr = 0; for (int j = 0; j < n; j++) { if (cur[j] != -1) continue; cur[j] = k[ptr++]; } SparseTable stmax(all(cur), [](int a, int b) { return max(a, b); }); int ans = 0; for (auto [l, r]: segs) { if (r < i or l > i) continue; ans += stmax.get(l, r) == R; } if (chmax(best, ans)) { id = i; } } return id; } i32 GetBestPosition(i32 N, i32 C, i32 R, i32 *K, i32 *S, i32 *E) { vec<int> k(K, K + N - 1); vec<pair<int, int>> segs; for (int i = 0; i < C; i++) { segs.emplace_back(S[i], E[i]); } return solve(N, C, R, k, segs); }

Compilation message (stderr)

tournament.cpp: In instantiation of 'SparseTable<it>::SparseTable(it, it, std::function<typename std::remove_reference<decltype (* declval<it>())>::type(typename std::remove_reference<decltype (* declval<it>())>::type, typename std::remove_reference<decltype (* declval<it>())>::type)>) [with it = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; typename std::remove_reference<decltype (* declval<it>())>::type = long long int]':
tournament.cpp:212:75:   required from here
tournament.cpp:162:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int>, std::allocator<std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for (int i = 1; i < t.size(); i++)
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...