Submission #581094

#TimeUsernameProblemLanguageResultExecution timeMemory
581094wdjpngBoarding Passes (BOI22_passes)C++17
0 / 100
2066 ms1612 KiB
#include <bits/stdc++.h> #define int long long #define double long double #define rep(i,n) for(int i =0; i<n; i++) #define all(a) a.begin(),a.end() using namespace std; string s; int n; double f(int n) { return ((double) n)*((double) (n-1))/4.0; } string ord; vector<double>mem; vector<vector<int>>pos; int g; // cost to add the group gr with all members of that group with and index <= to maxi boarding on the left double cost(int bor, int gr, int maxi) { double sum = 0; int firstr = maxi+1; sum+=f(pos[gr].size()-firstr) + f(firstr); vector<int>otherpos; rep(i,n) if(((1<<(s[i]-'A'))&bor)==0) otherpos.push_back(i); rep(i,firstr) { sum+=upper_bound(all(otherpos),pos[gr][i])-otherpos.begin(); } for(int i = firstr; i < pos[gr].size(); i++) sum+=otherpos.end()-upper_bound(all(otherpos),pos[gr][i]); return sum; } vector<int>lookup; double dfs(int bor) { if(mem[bor]>-0.9) return mem[bor]; double sol = 1e18; rep(i,g) { if(!((1<<i)&bor)) continue; int nbor = bor^(1<<i); // int start = -1, end = pos[i].size()-1; // while(end-start>1) // { // int c = (start+end)/2; // double l =cost(bor,i,c), r=cost(bor,i,c+1); // if(r>=l) end=c; // else start=c; // }; // // sol=min(sol, cost(bor,i,end)+dfs(nbor)); vector<int>otherpos; rep(i,n) if(((1<<(s[i]-'A'))&bor)==0) otherpos.push_back(i); rep(firstr,pos[i].size()) { double sum = f(pos[i].size()-firstr) + f(firstr); rep(j,firstr) sum+=upper_bound(all(otherpos),pos[i][j])-otherpos.begin(); for(int j = firstr; j < pos[i].size(); j++) sum+=otherpos.end()-upper_bound(all(otherpos),pos[i][j]); sol=min(sol,sum+dfs(nbor)); } } return mem[bor] = sol; } signed main() { cin>>s; s.size(); n=s.size(); cout.precision(300); char maxx=0; rep(i,n) maxx=max(maxx, s[i]); g=maxx-'A'+1; pos.resize(g); rep(i,n) pos[(s[i]-'A')].push_back(i); lookup.assign(g,0); rep(i,g) lookup[i]=i; mem.assign(1<<g,-1.0); mem[0]=0; cout<<dfs((1<<g)-1)<<'\n'; }

Compilation message (stderr)

passes.cpp: In function 'long double cost(long long int, long long int, long long int)':
passes.cpp:39:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = firstr; i < pos[gr].size(); i++) sum+=otherpos.end()-upper_bound(all(otherpos),pos[gr][i]);
      |                         ~~^~~~~~~~~~~~~~~~
passes.cpp: In function 'long double dfs(long long int)':
passes.cpp:5:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,n) for(int i =0; i<n; i++)
......
   69 |         rep(firstr,pos[i].size())
      |             ~~~~~~~~~~~~~~~~~~~~ 
passes.cpp:69:9: note: in expansion of macro 'rep'
   69 |         rep(firstr,pos[i].size())
      |         ^~~
passes.cpp:73:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for(int j = firstr; j < pos[i].size(); j++) sum+=otherpos.end()-upper_bound(all(otherpos),pos[i][j]);
      |                                 ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...