제출 #423573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423573		Knps4422	Crossing (JOI21_crossing)	C++14	26 / 100	7052 ms	9516 KiB

Main

//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
typedef complex<int> point;
const int nmax = 2005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = 1e9+10;
const int sq = 5000;

pair <int,pair<int,int>> compune(pair <int,pair<int,int>> a , pair <int,pair<int,int>> b){
	pair <int,pair<int,int>> c;
	c.fr = (2*a.fr + 2*b.fr)%3;
	c.sc.fr = (2*a.sc.fr + 2*b.sc.fr)%3;
	c.sc.sc = (2*a.sc.sc + 2*b.sc.sc)%3;
	return c;
}
int wtf(char ch){
	return (ch == 'J'? 0 : (ch == 'O' ? 1 : 2));
}
int n, q;
string s1,s2,s3;
string t;
vec < vec<int>> reach;

string check(){
	for(auto vcvc : reach){
		for(int i = 0; i <= n; i++){
			if(i == n)return "Yes\n";
			if(vcvc[i] != wtf(t[i]))break;
		}
	}
	return "No\n";
}
int main(){
	cin >> n;

	cin >> s1 >> s2 >> s3;
	set < pair<int,pair<int,int>> > proc, nw;
	nw.insert({1,{0,0}});
	nw.insert({0,{1,0}});
	nw.insert({0,{0,1}});
	while(nw.size()){
		auto conf = *nw.begin();
		nw.erase(nw.begin());
		for(auto conf2 : proc){
			auto conf3 = compune(conf,conf2);
			if(proc.find(conf3) == proc.end() && nw.find(conf3) == nw.end() && conf3 != conf){
				nw.insert(conf3);
			}
		}
		proc.insert(conf);
	}
	for(auto conf : proc){
		vec <int> xd (n);
		for(int i = 0 ; i < n; i++){
			xd[i] += wtf(s1[i]) * conf.fr;
		}
		for(int i = 0 ; i < n; i++){
			xd[i] += wtf(s2[i]) * conf.sc.fr;
		}
		for(int i = 0 ; i < n; i++){
			xd[i] += wtf(s3[i]) * conf.sc.sc;
			xd[i] %= 3;
		}
		//cout << conf.fr << ' ' << conf.sc.fr << ' ' << conf.sc.sc << ':';
 		reach.pb(xd);
	}
	
	cin >> q;
	cin >> t;
	cout << check();
	while(q--){
		int l , r;
		char chch;
		cin >> l >> r >> chch;
		for(int i = l; i <= r; i++){
			t[i-1] = chch;
		}
		//cout << t << ' ';
		cout << check();
	}
}

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