제출 #1142304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142304		SmuggingSpun	Crossing (JOI21_crossing)	C++20	100 / 100	188 ms	11220 KiB

Main

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
int n;
string sa, sb, sc;
namespace sub1{
	void solve(){
		int q;
		string t;
		cin >> q >> t;
		cout << (t == sa ? "Yes\n" : "No\n");
		for(int _ = 0; _ < q; _++){
			int l, r;
			char c;
			cin >> l >> r >> c;
			for(int i = l - 1; i < r; i++){
				t[i] = c;
			}
			cout << (t == sa ? "Yes\n" : "No\n");
		}
	}
}
namespace sub234{
	const int base = 397;
	const int mod = 1e9 + 33;
	void solve(){
		auto get_merge = [&] (string a, string b){
			string ans = "";
			for(int i = 0; i < n; i++){
				if(a[i] != b[i]){
					ans += char(a[i] ^ b[i] ^ 'J' ^ 'O' ^ 'I');
				}
				else{
					ans += a[i];
				}
			}
			return ans;
		};
		vector<int>pw(n + 1);
		for(int i = pw[0] = 1; i <= n; i++){
			pw[i] = 1LL * pw[i - 1] * base % mod;
		}
		vector<int>init;
		unordered_map<string, bool>cnt;
		cnt[sa] = cnt[sb] = cnt[sc] = true;
		queue<string>q;
		q.push(sa);
		q.push(sb);
		q.push(sc);
		while(!q.empty()){
			string u = q.front();
			q.pop();
			string A = get_merge(u, sa), B = get_merge(u, sb), C = get_merge(u, sc);
			if(!cnt[A]){
				cnt[A] = true;
				q.push(A);
			}
			if(!cnt[B]){
				cnt[B] = true;
				q.push(B);
			}
			if(!cnt[C]){
				cnt[C] = true;
				q.push(C);
			}
		}
		for(auto& [s, foo] : cnt){
			int init_sum = 0;
			for(int i = 0; i < n; i++){
				init_sum = (1LL * s[i] * pw[i + 1] % mod + init_sum) % mod;
			}
			init.emplace_back(init_sum);
		}
		for(int i = 1; i <= n; i++){
			pw[i] = (pw[i] + pw[i - 1]) % mod;
		}
		vector<pair<int, char>>st(n << 2 | 3);
		int cnt_query;
		string t;
		cin >> cnt_query >> t;
		t = '#' + t;
		auto build = [&] (auto&& self, int id, int l, int r){
			if(l == r){
				st[id] = make_pair(1LL * (pw[l] - pw[l - 1] + mod) * t[l] % mod, '#');
				return; 
			}
			int m = (l + r) >> 1;
			self(self, id << 1, l, m);
			self(self, id << 1 | 1, m + 1, r);
			st[id] = make_pair((st[id << 1].first + st[id << 1 | 1].first) % mod, '#');
		};
		auto push_down = [&] (int id, int l, int r, int m){
			if(st[id].second != '#'){
				st[id << 1] = make_pair(1LL * (pw[m] - pw[l - 1] + mod) * st[id].second % mod, st[id].second);
				st[id << 1 | 1] = make_pair(1LL * (pw[r] - pw[m] + mod) * st[id].second % mod, st[id].second);
				st[id].second = '#';
			}
		};
		auto update = [&] (auto&& self, int id, int l, int r, int u, int v, char x){
			if(l > v || r < u){
				return;
			}	
			if(u <= l && v >= r){
				st[id] = make_pair(1LL * (pw[r] - pw[l - 1] + mod) * x % mod, x);
				return;
			}
			int m = (l + r) >> 1;
			push_down(id, l, r, m);
			self(self, id << 1, l, m, u, v, x);
			self(self, id << 1 | 1, m + 1, r, u, v, x);
			st[id].first = (st[id << 1].first + st[id << 1 | 1].first) % mod;
		};
		build(build, 1, 1, n);
		cout << (find(init.begin(), init.end(), st[1].first) != init.end() ? "Yes\n" : "No\n");
		for(int _ = 0; _ < cnt_query; _++){
			int l, r;
			char c;
			cin >> l >> r >> c;
			update(update, 1, 1, n, l, r, c);
			cout << (find(init.begin(), init.end(), st[1].first) != init.end() ? "Yes\n" : "No\n");
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> sa >> sb >> sc;
	if(n <= 100 && sa == sb && sb == sc){
		sub1::solve();
	}
	else{
		sub234::solve();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:128:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51