Submission #950009

#TimeUsernameProblemLanguageResultExecution timeMemory
950009De3b0oChorus (JOI23_chorus)C++14
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> #define ll long long #define F first #define S second #define in insert #define pb push_back #define ppb pop_back() #define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define cans cout << ans << "\n"; #define yes cout << "Yes" << "\n"; #define no cout << "No" << "\n"; #define pll pair<ll,ll> #define lin cout << "\n"; #define sqr 340 #define mod 1000000007 #define mid ((l+r)/2) #define lc (2*n) #define rc (2*n+1) using namespace std; ll fp(ll x , ll y) { if(y==0) return 1; ll z = fp(x,y/2); if(y&1) return z*z*x; else return z*z; } int sqrot(ll x) { int l = 0 , r = INT_MAX; while(l<=r) { if(mid*mid>=x) r=mid-1; else l=mid+1; } return r+1; } ll cel(ll x , ll y) { return x/y + bool(x%y); } string tb(ll x) { string s = ""; while(x>0) { if(x&1) s+='1'; else s+='0'; x/=2; } while(s.size()<60) s+='0'; return s; } ll fb(string s) { ll x = 0; ll c = 1; for(int8_t i = 0 ; 60>i ; i++) { if(s[i]=='1') x+=c; c*=2; } return x; } ll n , k; string s; bool check(ll x) { string t = s; set<ll> idx; for(int i = 0 ; 2*n>i ; i++) if(s[i]=='B') idx.in(i); ll x1 = x; ll y = 0; while(!idx.empty()) { if(x1==0) break; ll f = y; ll c = 0; ll y1; while(!idx.empty()) { auto it = idx.begin(); ll ff = *it; if(x1>=(ff-f-1)*c) { x1-=(ff-f-1)*c; f=ff; c++; y1=*it+1; idx.erase(it); continue; } else break; } for(int i = y ; f>=i ; i++) t[i]='A'; for(int i = f ; i>f-c ; i--) t[i]='B'; ll z = f-c+1-y; z-=c; y=y1; while(z--&&!idx.empty()) { auto it = idx.begin(); y=*it+1; idx.erase(it); } } idx.clear(); for(int i = 0 ; 2*n>i ; i++) if(t[i]=='B') idx.in(i); y = 0; bool vis[2*n]={0}; ll p = 0; bool e = 0; for(int i = 0 ; 2*n>i ; i++) { if(vis[i]) continue; if(t[i]=='A') { p++; continue; } if(t[i]=='B'&&p==0) { e=1; continue; } y++; while(p--) { auto it = idx.begin(); vis[*it]=1; idx.erase(it); } p=0; } if(e||y>k) return 0; else return 1; } int main() { //d3 cin >> n >> k; cin >> s; ll l = 0 , r = n*n; ll ans; while(l<=r) { if(check(mid)) { ans=mid; r=mid-1; } else l=mid+1; } cans }

Compilation message (stderr)

chorus.cpp: In function 'bool check(long long int)':
chorus.cpp:115:17: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |         for(int i = y ; f>=i ; i++)
      |                 ^
#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...