Submission #296203

#	Time	Username	Problem	Language	Result	Execution time	Memory
296203		maximath_1	Monochrome Points (JOI20_monochrome)	C++11	100 / 100	18 ms	3604 KiB

monochrome

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string.h>
#include <set>
#include <math.h>
#include <numeric>
#include <assert.h>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <queue>
#include <random>
#include <chrono>
#include <limits.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define endl "\n"
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST_multiset;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const ll inf = 1e9 + 69;
const ld pi = 3.14159265358979323L;
const ld eps = 1e-15;
 
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
int setIO_count = 0;
void setIO(string s = "", bool inx = 0, bool outx = 0){
	if(!setIO_count){
		unsyncIO();
		setIO_count = 1;
	}
	if(s.size()){ //output only
		if(inx) setIn(s + ".in");
		if(outx) setOut(s + ".out");
	}
}
 
#define gc getchar//_unlocked //can't for window server
#define pc putchar//_unlocked //can't for window server
ll inp(){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	ll rs = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		rs = (rs << 1) + (rs << 3) + (c - '0');
	if(neg) rs = -rs;
	return rs;
}
void pri(ll _n){
	ll N = _n, rev, count = 0;
	bool neg = false;
	if(N < 0){
		N = -N; neg = true;
	}
	rev = N;
	if(N == 0) {pc('0'); return;}
	if(neg) pc('-');
	while(rev % 10 == 0) {count ++; rev /= 10;}
	rev = 0;
	while(N != 0) {rev = (rev << 3) + (rev << 1) + N % 10; N /= 10;}
	while(rev != 0) {pc(rev % 10 + '0'); rev /= 10;}
	while(count --) pc('0');
}
 
const ll mod = 1e9 + 7;
const int N = 200005;

int n, v[N * 2], pref[N];
string s;

int main(){
	setIO();
	
	cin >> n >> s;
	for(int i = 0; i < 2 * n; i ++)
		v[i] = (s[i] == 'W' ? 1 : -1);

	for(int i = 0; i < n; i ++){
		if(i == 0) pref[i] = v[i] * (v[i] == v[n + i]);
		else pref[i] = pref[i - 1] + v[i] * (v[i] == v[n + i]);
	}
	sort(pref, pref + n);
 
 	ll ans = n * 1ll * (n - 1) / 2;
 	for(int i = 0; i < n; i ++)
 		ans -= abs(pref[n / 2] - pref[i]);
 	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'void setIn(std::string)':
monochrome.cpp:33:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   33 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
monochrome.cpp: In function 'void setOut(std::string)':
monochrome.cpp:34:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65