Submission #1156982

#TimeUsernameProblemLanguageResultExecution timeMemory
1156982at128Arranging Shoes (IOI19_shoes)C++20
100 / 100
85 ms19016 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif typedef tree< int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define all(v) ((v).begin()), ((v).end()) #define sz(v) ((int)((v).size())) #define pb push_back typedef long long ll; long long count_swaps(std::vector<int> s1) { int n; n=s1.size()/2; vector<int>v(2*n); vector<int>p(n+1),ne(n+1); vector<vector<int>>gp(n+1); vector<vector<int>>gne(n+1); for(int i=0;i<2*n;i++){ v[i]=s1[i]; if(v[i]>0){ gp[v[i]].pb(i); }else{ gne[-v[i]].pb(i); } } ll res=0,c=0; ordered_set s; for(int i=0;i<2*n;i++){ if(v[i]==INT_MAX){ continue; } c++; if(v[i]>0){ p[v[i]]++; int j=gne[v[i]][ne[v[i]]++]; v[j]=INT_MAX; ll p1=s.size()-s.order_of_key(i); ll p2=s.size()-s.order_of_key(j); s.insert(j); res+=max(0ll,(j-i-(p1-p2))); }else{ ne[-v[i]]++; int j=gp[-v[i]][p[-v[i]]++]; v[j]=INT_MAX; ll p1=s.size()-s.order_of_key(i); ll p2=s.size()-s.order_of_key(j); s.insert(j); res+=max(0ll,(j-i-(p1-p2)-1)); } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...