Submission #683821

#TimeUsernameProblemLanguageResultExecution timeMemory
683821FystyMonochrome Points (JOI20_monochrome)C++17
35 / 100
389 ms6108 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define MottoHayaku ios::sync_with_stdio(false);cin.tie(0); #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define F first #define S second #define pb push_back mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N=4e5+5; struct BIT { int a[N]; void init() { rep1(i,N-1) a[i]=0; } void upd(int x,int val) { for(;x<N;x+=x&-x) a[x]+=val; } int qry(int x) { int ret=0; for(;x;x-=x&-x) ret+=a[x]; return ret; } } bit; int n,to[N]; vector<int> a,b; string s; int getans(int i) { i=(i%n+n)%n; rep(j,n) { to[a[j]]=b[(j+i)%n]; to[b[(j+i)%n]]=a[j]; } bit.init(); int tot=0; rep1(j,n*2) { if(to[j]<j) bit.upd(j,-1); else { tot+=bit.qry(to[j]); bit.upd(to[j],1); } } return tot; } signed main() { MottoHayaku cin>>n>>s; //rep(i,n) s+="BW"; //shuffle(s.begin(),s.end(),rng); //cout<<n<<"\n"<<s<<"\n"; rep(i,n*2) { if(s[i]=='B') a.pb(i+1); else b.pb(i+1); } int l=rng()%n; int r=l+n-1; while(l<r) { int mid=l+r+1>>1; int x=getans(mid)-getans(mid-1); if(x>0) l=mid; else r=mid-1; } cout<<getans(l)<<"\n"; }

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:76:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int mid=l+r+1>>1;
      |                 ~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...