Submission #850026

#TimeUsernameProblemLanguageResultExecution timeMemory
850026Mr_PhMonochrome Points (JOI20_monochrome)C++14
0 / 100
1 ms456 KiB
///Never gonna give you up. #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; typedef long long int lli; typedef unsigned long long ull; using namespace std; using namespace __gnu_pbds; template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>; const ll mod=(ll)1e9+7; const ll mod1=998244353; ///the defines :) //#define endl '\n' #define vi vector<int> #define vll vector<ll> #define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i]; #define all(arr) arr.begin(),arr.end() #define allr(arr) arr.rbegin(),arr.rend() #define sz size() #define int long long void preprocess() {} void solve() { int n; cin>>n; string s; cin>>s; map<int,char>mp; vi arr; vi arr1; int xd=0; for(int i=0;i<s.sz;i++) { if(s[i]=='W')arr.push_back(i+1); else arr1.push_back(i+1); } do { bool valid=false; for(int i=0;i<arr.sz-1;i++) { if(s[arr[i]-1]==s[arr1[i+1]-1]) { valid=true; break; } } if(valid)continue; map<pair<int,int>,int>mp; for(int i=0;i<arr.sz-1;i++) mp[{arr[i],arr1[i+1]}]++; int ans=0; for(int i=0;i<arr.sz-1;i++) { int lol=0; map<pair<int,int>,int>mp1; int l=arr[i],r=arr1[i+1]; while(!mp1[{l,r}]&&!mp1[{r,l}]) { l--,r++; if(l<1)l=n; if(r>n)r=1; mp1[{l,r}]++; mp1[{r,l}]++; lol+=mp[{l,r}]|mp[{r,l}]; } map<pair<int,int>,int>mp2; l=arr[i],r=arr1[i+1]; while(!mp2[{l,r}]&&!mp2[{r,l}]) { l++,r--; if(r<1)r=n; if(l>n)l=1; mp2[{l,r}]++; mp2[{r,l}]++; lol+=mp[{l,r}]|mp[{r,l}]; } // cout<<lol<<endl; ans+=((n-1)-lol); } xd=max(xd,ans); // cout<<"-----------"<<endl; }while(next_permutation(all(arr))); cout<<xd/2<<endl; } signed main() { // freopen("div7.in","r",stdin); //freopen("div7.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); preprocess(); //bla(); int t=1; //cin>>t; while(t--) solve(); }

Compilation message (stderr)

monochrome.cpp: In function 'void solve()':
monochrome.cpp:34:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<s.sz;i++)
      |                  ^
monochrome.cpp:42:22: 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]
   42 |         for(int i=0;i<arr.sz-1;i++)
      |                     ~^~~~~~~~~
monochrome.cpp:52:22: 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]
   52 |         for(int i=0;i<arr.sz-1;i++)
      |                     ~^~~~~~~~~
monochrome.cpp:55:22: 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]
   55 |         for(int i=0;i<arr.sz-1;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...