Submission #37028224

---

Source Code Expand

//O(NQ) ....
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <random>
#include <cassert>
#include <unordered_map>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

mt19937 mt(2521);

int naive(string s) {
	queue<string> que;
	unordered_map<string, int> dp;
	map<string, string> prevS;
	vector<vector<int>> perms = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};

	que.push(s);
	dp[s] = 0;
	int ret = -1;
	string ret_s;
	while (!que.empty()) {
		string now = que.front(); que.pop();
		int n = now.length();

		bool check = true;
		for (int i = 0; i < n - 1; i++) {
			if (now[i] != now[i + 1]) { check = false; break; }
		}
		if (check) { ret = dp[now]; ret_s = now; break; }

		for (int i = 0; i < 6; i++) {
			for (int l = 0; l < n; l++) {
				string t;
				for (int r = l; r < n; r++) {
					int x = perms[i][now[r] - 'A'];
					t += (char)(x + 'A');
					string nxt;
					for (int k = 0; k < l; k++) nxt += now[k];
					nxt += t;
					for (int k = r + 1; k < n; k++) nxt += now[k];
					if (dp.find(nxt) == dp.end()) {
						dp[nxt] = dp[now] + 1;
						prevS[nxt] = now;
						que.push(nxt);
					}
				}
			}
		}
	}

	/*for (int i = 0; i < ret; i++) {
		cout << ret_s << endl;
		ret_s = prevS[ret_s];
	}
	cout << ret_s << endl;*/
	return ret;
}

int greedy(string s) {
	int i;
	string ss;
	rep(i, s.length()) {
		if (i > 0 && s[i - 1] == s[i]) continue;
		ss += s[i];
	}
	//cout << "ss = " << ss << endl;

	int ret = ss.length();
	int n = ss.length();
	typedef pair<int, char> P;
	for (char c = 'A'; c <= 'C'; c++) {
		vector<P> vec;
		int len = 0; char first_char = '-';
		
		//cout << "c = " << c << endl;
		rep(i, n) {
			if (ss[i] == c) {
				if (len > 0) vec.push_back(P(len, first_char));
				len = 0;
				continue;
			}
			if (len == 0) first_char = ss[i];
			len++;
		}
		if (len > 0) vec.push_back(P(len, first_char));

		int cst = 0;
		
		rep(i, vec.size()) {
			cst += vec[i].first / 2 + 1;
		}

		int cnt = 0;
		for (int i = 0; i < vec.size(); i++) {
			if (vec[i].first % 2 == 0) cnt++;
		}
		cst -= cnt / 2;
		//cout << "cst = " << cst << endl;
		ret = min(ret, cst);
	}
	return ret;
}

void solve_input() {
	int n, Q;
	cin >> n >> Q;
	string s;
	cin >> s;
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r; l--; r--;

		string t;
		for (int j = l; j <= r; j++) t += s[j];
		cout << greedy(t) << endl;
	}
}

signed main() {
	solve_input();
	return 0;

	//naive("ABCCACABC");
	//return 0;

	/*int n = 10, i;
	int T = 2000;

	for (int t = 0; t < T; t++) {
		cout << "t = " << t << endl;
		string s;
		rep(i, n) {
			s += (char)(mt() % 3 + 'A');
		}
		int res1 = naive(s);
		int res2 = greedy(s);
		if (res1 != res2) {
			cout << s << " " << res1 << " " << res2 << endl;
			break;
		}
	}

	return 0;*/
}

Submission Info

Compile Error

./Main.cpp: In function ‘long long int greedy(std::string)’:
./Main.cpp:17:32: 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]
   17 | #define rep(i, n) for(i = 0; i < n; i++)
......
   74 |  rep(i, s.length()) {
      |      ~~~~~~~~~~~~~              
./Main.cpp:74:2: note: in expansion of macro ‘rep’
   74 |  rep(i, s.length()) {
      |  ^~~
./Main.cpp:17:32: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<std::pair<long long int, char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   17 | #define rep(i, n) for(i = 0; i < n; i++)
......
  101 |   rep(i, vec.size()) {
      |       ~~~~~~~~~~~~~             
./Main.cpp:101:3: note: in expansion of macro ‘rep’
  101 |   rep(i, vec.size()) {
      |   ^~~
./Main.cpp:106:21: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<std::pair<long long int, char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  106 |   for (int i = 0; i < vec.size(); i++) {
      |                   ~~^~~~~~~~~~~~

Judge Result