제출 #1336495

#제출 시각아이디문제언어결과실행 시간메모리
1336495alibiCrossing (JOI21_crossing)C++20
26 / 100
7092 ms4528 KiB
#include <bits/stdc++.h>
#include <random>
#include <chrono>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#define pb push_back
#define all(x) (x).begin(), (x).end()
//#define sz(x) (int) (x.size())
#define F first
#define S second
#define in insert
using namespace std;
using ll = long long;
 
const int N = 1e6+5;
const int pw = 31;
const ll inf = 1e18;
const int mod = 1e9+7;

char wor(char a, char b) {
    if (a == b) return a;
    return (char)(226 - (a + b));
}

ll get(string s, int n){
	ll h = 0;
	ll p = 1;
	for(int i = 0 ;i < n;i++){
		h = (h + (s[i] - 'A' + 1) * p) % mod;
		p = (p*pw) % mod;
	}
	return h;
}

bool check(const ll &x , const vector<ll> &y){
	bool ok = false;
	for(auto i : y){
		if(i == x){
			ok = true;
		}
	}
	return ok;
}

void solve() {
	int n;cin >> n;
	vector<string>var;
	string s1 ,s2 ,s3;
	cin >> s1 >> s2 >> s3;
	var.pb(s1);
	var.pb(s2);
	var.pb(s3);
	string ab = "" , bc = "" , ca = "";
	for(int i = 0 ; i < n;i++){
		ab.pb(wor(s1[i] , s2[i]));
		bc.pb(wor(s2[i] , s3[i]));
		ca.pb(wor(s3[i] , s1[i]));
	}
	var.pb(ab);
	var.pb(bc);
	var.pb(ca);
	string abc = "" , bca = "" , cab = "";
	for(int i = 0; i < n;i++){
		abc.pb(wor(ab[i] , s3[i]));
		bca.pb(wor(bc[i] , s1[i]));
		cab.pb(wor(ca[i] , s2[i]));
	}
	var.pb(abc);
	var.pb(bca);
	var.pb(cab);
	vector<ll>hash;
	
	for(auto &s : var){
		hash.pb(get(s , n));
	}
	
	int q;cin >> q;
	
	string T;cin >> T;
	
	if(check(get(T , n) , hash)){
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
	
	while(q--){
		int l , r;
		char c;
		cin >> l >> r >> c;
		
		for(int i = l-1;i < r;i++){
			T[i] = c;
		}
		
		if(check(get(T , n) , hash)){
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
		
	}
	
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int TT = 1;
//    cin >> TT;
    while (TT--) solve();
    return 0;
}//
 
 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...