제출 #1122010

#제출 시각아이디문제언어결과실행 시간메모리
1122010vjudge1Boarding Passes (BOI22_passes)C++17
60 / 100
1861 ms1048576 KiB
// Bolatulu #include <bits/stdc++.h> // #include <art.h> /* #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") */ typedef long long ll; typedef unsigned long long ull; typedef double db; #define pb push_back #define eb emplace_back #define ins insert #define F first #define S second #define md (tl+tr)/2 #define TL v+v,tl,md #define TR v+v+1,md+1,tr #define Tl t[v].l,tl,md #define Tr t[v].r,md+1,tr #define all(x) (x).begin(),(x).end() #define yes cout << "YES\n" #define no cout << "NO\n" #define int long long // #define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout); using namespace std; int binpow(int a,int n,int M) { if (n==0) return 1; if (n%2!=0) return (a * binpow(a,n-1,M))%M; int z=binpow(a,n/2,M); return (z*z)%M; } const ll INF = 1e18+7; const int N = 1e5+7; int n,dp[N],a[N],c[N]; string s; vector <int> v[N],d[N]; void solve() { cin >> s; n=s.size(); s=" "+s; int g=0; for (int i=1;i<=n;i++) { g=max(g,(int)(s[i]-'A'+1)); d[s[i]-'A'].pb(i); } for (int mask=1;mask<(1<<g);mask++) { int mn=-1; for (int i=0;i<g;i++) { c[i]=0; if (mask>>i&1) mn=i; } int j=0,f=(mask^(1<<mn)); for (auto now : v[f]) { while (j<d[mn].size() and d[mn][j]<now) { v[mask].pb(d[mn][j]); j++; } v[mask].pb(now); } while (j<d[mn].size()) { v[mask].pb(d[mn][j]); j++; } int x=0; for (auto i : v[mask]) { int bit=s[i]-'A'; if (mask>>bit&1) { a[i]=x*2-c[bit]; x++; c[bit]++; } } for (int i=0;i<g;i++) c[i]=0; x=0; reverse(all(v[mask])); for (auto i : v[mask]) { int bit=s[i]-'A'; if (mask>>bit&1) { a[i]=min(a[i],x*2-c[bit]); x++; c[bit]++; } } for (int i=0;i<g;i++) c[i]=0; reverse(all(v[mask])); for (auto i : v[mask]) { int bit=s[i]-'A'; if (mask>>bit&1) c[bit]+=a[i]; } dp[mask]=INF; for (int i=0;i<g;i++) { if (mask>>i&1) dp[mask]=min(dp[mask^(1<<i)]+c[i],dp[mask]); } } int ans=dp[(1<<g)-1]; if (ans%2!=0) cout << ans/2 << ".5"; else cout << ans/2; } signed main() { // file("jenga"); ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int test = 1; // cin >> test; while (test--) { solve(); if (test) cout << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

passes.cpp: In function 'void solve()':
passes.cpp:65:21: 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]
   65 |             while (j<d[mn].size() and d[mn][j]<now) {
      |                    ~^~~~~~~~~~~~~
passes.cpp:71:17: 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]
   71 |         while (j<d[mn].size()) {
      |                ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...