Submission #463973

#TimeUsernameProblemLanguageResultExecution timeMemory
463973wind_reaperArranging Shoes (IOI19_shoes)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "" /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> */ using namespace std; // using namespace __gnu_pbds; using namespace chrono; // mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); /* template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; */ //***************** CONSTANTS ***************** //***************** GLOBAL VARIABLES ***************** //***************** AUXILIARY STRUCTS ***************** struct FenwickTree{ vector<int> tree; int n; FenwickTree(int N){ tree.resize(N + 1); n = N; } void add(int x, int v){ for(; x <= n; x += (x & (-x))) tree[x] += v; } int get(int x){ int sum = 0; for(; x; x -= (x & (-x))) sum += tree[x]; return sum; } }; //***************** MAIN BODY ***************** int64_t count_swaps(vector<int> S){ int N = S.size() / 2; vector<int> ord[N+1]; for(int i = 1; i <= 2*N; i++){ ord[abs(S[i-1])].push_back({(S[i-1] < 0 ? -i : i)}); } int64_t ret = 0; FenwickTree X(2*N); for(int i = 1; i <= 2*N; i++) X.add(i, 1); for(int i = 1; i <= N; i++){ sort(ord[i].begin(), ord[i].end()); int z = ord[i].size() >> 1; for(int j = 0; j < z; j++){ int l = -ord[i][j], r = ord[i][2 * z - j - 1]; if(l > r){ swap(l, r); ret++; } // cout << i << ' ' << l << ' ' << r << ' ' << ret << '\n'; ret += X.get(r - 1) - X.get(l); // X.add(r, -1); // X.add(l, -1); } } return ret; } //***************** ***************** // int32_t main(){ // vector<int> S = {-2, 2, 2, -2, -2, 2}; // cout << count_swaps(S); // } // int32_t main(){ // ios_base::sync_with_stdio(NULL); // cin.tie(NULL); // #ifdef LOCAL // auto begin = high_resolution_clock::now(); // #endif // int tc = 1; // cin >> tc; // for (int t = 0; t < tc; t++) // solve(); // #ifdef LOCAL // auto end = high_resolution_clock::now(); // cout << fixed << setprecision(4); // cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl; // #endif // return 0; // } /* If code gives a WA, check for the following : 1. I/O format 2. Are you clearing all global variables in between tests if multitests are a thing 3. Can you definitively prove the logic 4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity, use faster io */

Compilation message (stderr)

shoes.cpp:2:10: error: empty filename in #include
    2 | #include ""
      |          ^~