Submission #515821

#TimeUsernameProblemLanguageResultExecution timeMemory
515821VictorEkoeko (COCI21_ekoeko)C++17
20 / 110
7 ms1740 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout<<#x<<" = "<<x<<endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; struct fenwick_tree { vi ft; fenwick_tree(int n) { ft.assign(n+1,0); } int rsq(int i) { int sum=0; for(;i;i-=i&-i) sum+=ft[i]; return sum; } int rsq(int i,int j) {return rsq(j)-rsq(i-1);} void update(int i,int v) { for(;i<sz(ft);i+=i&-i) ft[i]+=v; } }; int cnt[150],n,ans=0; vi lets[150]; string word; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); memset(cnt,0,sizeof(cnt)); cin>>n>>word; trav(let,word) ++cnt[let]; rep(i,0,150) cnt[i]/=2; string p1="",p2=""; trav(let,word) { if(cnt[let]) { --cnt[let]; p1+=let; ans+=sz(p2); } else { p2+=let; lets[let].pb(sz(p2)); } } word=p1+p2; //cout<<word<<endl; rep(i,0,150) reverse(all(lets[i])); fenwick_tree fenwick(n); int target=1; trav(let,p1) { int pos=lets[let].back(); lets[let].pop_back(); fenwick.update(pos,1); pos+=fenwick.rsq(pos+1, n); //cout<<"let = "<<let<<" pos = "<<pos<<" target = "<<target<<endl; ans+=pos-target; assert(pos>=target); ++target; } cout<<ans<<endl; return 0; }

Compilation message (stderr)

Main.cpp: In member function 'void fenwick_tree::update(int, int)':
Main.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(;i<sz(ft);i+=i&-i) ft[i]+=v;
      |               ^
Main.cpp: In function 'int main()':
Main.cpp:63:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |     trav(let,word) ++cnt[let];
      |                          ^~~
Main.cpp:68:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   68 |         if(cnt[let]) {
      |                ^~~
Main.cpp:69:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |             --cnt[let];
      |                   ^~~
Main.cpp:75:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |             lets[let].pb(sz(p2));
      |                  ^~~
Main.cpp:86:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |         int pos=lets[let].back();
      |                      ^~~
Main.cpp:87:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |         lets[let].pop_back();
      |              ^~~
#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...