QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#657511 | #9463. 基础 ABC 练习题 | wrkwrk | 0 | 0ms | 3620kb | C++20 | 7.1kb | 2024-10-19 14:54:16 | 2024-10-19 14:54:17 |
answer
#include<bits/stdc++.h>
using namespace std;
bool st;
namespace _wrk{;
template<int mod>
struct modint{
int num;
const static __uint128_t brt=((__uint128_t)(1)<<(64))/mod;
modint(){
num=0;
}
modint(int x){
num=x%mod;
}
modint(long long x){
num=x%mod;
}
modint<mod>operator=(int x){
num=x%mod;
return (*this);
}
modint<mod>operator=(long long x){
num=x%mod;
return (*this);
}
modint<mod>operator=(modint<mod>x){
num=x.num;
return (*this);
}
modint<mod> operator+(modint<mod> c)const{
long long x=num+c.num;
return x>=mod?x-mod:x;
}
modint<mod> operator-(modint<mod> c)const{
long long x=num-c.num;
return x<0?x+mod:x;
}
modint<mod>operator*(modint<mod>c)const{
long long x=(long long)num*c.num;
x=x-mod*(brt*x>>64);
while(x>=mod)x-=mod;
return x;
}
modint<mod>fpof(long long x)const{
if(x<0)return inv().fpof(-x);
if(x==0)return 1;
auto c=((*this)*(*this)).fpof(x/2);
if(x&1)return c*(*this);
else return c;
}
struct modint_pow{
int pf;
modint_pow(int x){
pf=x;
}
modint_pow(modint<mod> x){
pf=x.num;
}
modint_pow operator+(modint_pow x){
return pf+x.pf;
}
};
modint_pow operator*(){
return modint_pow(num);
}
modint<mod> operator*(modint_pow x){
return (*this).fpof(x.pf);
}
modint<mod>inv()const{
return fpof(mod-2);
}
modint<mod>operator/(modint<mod>c){
return (*this)*c.inv();
}
operator int(){
return num;
}
modint<mod>operator+=(modint<mod> c){
return (*this)=(*this)+c;
}
modint<mod>operator-=(modint<mod> c){
return (*this)=(*this)-c;
}
modint<mod>operator*=(modint<mod> c){
return (*this)=(*this)*c;
}
modint<mod>operator/=(modint<mod> c){
return (*this)=(*this)/c;
}
modint<mod>operator-(){
return mod-num;
}
friend ostream& operator<<(ostream &w,modint<mod>&&x){
w<<x.num;
return w;
}
friend istream& operator>>(istream &w,modint<mod>&x){
w>>x.num;
x.num%=mod;
return w;
}
bool operator==(modint<mod>x){
return num==x.num;
}
};
template<int mod,class type>
modint<mod>operator+(type a,modint<mod>b){
return modint<mod>(a)+b;
}
template<int mod,class type>
modint<mod>operator-(type a,modint<mod>b){
return modint<mod>(a)-b;
}
template<int mod,class type>
modint<mod>operator*(type a,modint<mod>b){
return modint<mod>(a)*b;
}
template<int mod,class type>
modint<mod>operator/(type a,modint<mod>b){
return modint<mod>(a)/b;
}
#define int long long
template<class type,int N>
struct matrix{
type a[N+2][N+2];
int n;
type* operator[](int pos){
return a[pos];
}
matrix<type,N> operator*(matrix<type,N>b){
matrix<type,N>ans;
ans.n=n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
ans[i][j]+=a[i][k]*b[k][j];
}
}
}
return ans;
}
};
template<class type>
type fp(type a,int b){
if(b==0)return type();
if(b==1)return a;
type w=fp(a*a,b/2);
if(b%2)return w*a;
return w;
}
template<class type,int N>
struct backup_array{
type name[N+5];
vector<vector<pair<int,int>>>cc;
void new_array(){
cc.push_back(vector<pair<int,int>>());
}
backup_array(){
cc.resize(1);
}
struct x{
int id;
type* name;
vector<vector<pair<int,int>>> &cc;
operator type(){
return name[id];
}
type operator=(type w){
cc.back().push_back({id,name[id]});
name[id]=w;
return w;
}
};
x operator[](int pos){
return {pos,name,cc};
}
void backup(){
reverse(cc.back().begin(),cc.back().end());
for(auto &x:cc.back()){
name[x.first]=x.second;
}
cc.pop_back();
}
};
template<class type,int N>
struct Math{
type jc[N+5],inv[N+5],invjc[N+5];
Math(){
jc[0]=jc[1]=inv[1]=invjc[1]=invjc[0]=1;
for(int i=2;i<=N;i++){
jc[i]=jc[i-1]*type(i);
}
invjc[N]=type(1)/jc[N];
for(int i=N-1;i>=2;i--){
invjc[i]=invjc[i+1]*type(i+1);
}
for(int i=1;i<=N;i++){
inv[i]=invjc[i]*jc[i-1];
}
}
type binom(int a,int b){
return jc[a]*invjc[b]*invjc[a-b];
}
type catalan(int n){
return binom(2*n,n)/type(n+1);
}
};
template<class type,int num,int maxnum>
struct pows{
type w[maxnum+5];
pows(){
w[0]=type(1);
for(int i=1;i<=maxnum;i++)w[i]=w[i-1]*type(num);
}
type operator[](int pos){
return w[pos];
}
};
#ifdef use_seg_tree
template<class type,class laz_type,int len>
struct segment_tree{
type a[len<<2];
laz_type laz[len<<2];
void pushup(int now){
PUSHUP_VALUE
}
void pushdown(int now,int l,int r){
PUSHDOWN_VALUE
}
void build(int now,int l,int r){
if(l+1==r){
FIRST_VALUE
return;
}
LAZ_CLEAR
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid,r);
pushup(now);
}
void do1(int now,int l,int r,int L,int R,...){
if(l+1!=r)pushdown(now,l,r);
if(R<=l||r<=L)return;
if(L<=l&&r<=R){
FULL_BLOCK_VALUE
return;
}
int mid=(l+r)>>1;
do1(now<<1,l,mid,L,R,...);
do1(now<<1|1,mid,r,L,R,...);
pushup(now);
}
void do1_one(int now,int l,int r,int p,...){
if(l+1!=r)pushdown(now,l,r);
if(l+1==r){
DO1_VALUE
return;
}
int mid=(l+r)>>1;
if(p<mid)do1_one(now<<1,l,mid,p,...);
else do1_one(now<<1|1,mid,r,p,...);
pushup(now);
}
type qu1(int now,int l,int r,int L,int R){
if(l+1!=r)pushdown(now,l,r);
if(R<=l||r<=L)return BASE_VALUE
if(L<=l&&r<=R)return a[now];
int mid=(l+r)>>1;
return RETURN_VALVE qu1(now<<1,l,mid,L,R)+qu1(now<<1|1,mid,r,L,R);
}
type qu1_one(int now,int l,int r,int p){
if(l+1!=r)pushdown(now,l,r);
if(l+1==r)return a[now];
int mid=(l+r)>>1;
if(p<mid)return qu1_one(now<<1,l,mid,p);
else return qu1_one(now<<1|1,mid,r,p);
}
};
#endif
//#define mod 998244353
//#define mint modint<mod>
//pows<mint,2,1000006>tp;
//Math<mint,1000006>math;
//vector<int>g[1000006]
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
string t;
cin>>t;
string p;
cin>>p;
p='#'+p;
if(n!=60){
cout<<"-1\n";
continue;
}
int ans=0;
for(int i=0;i<=n;i++){
for(int j=0;i+j<=n;j++){
if(s[i]=='1'&&t[j]=='1'){
int res=1;
int k=n-i-j;
// i ABC
// j BCA
// k CAB
int na=0,nb=0,nc=0;
for(int f=1;f<=3*n;f++){
if(p[f]=='A'){
if(!((na<i)||(i<=na&&na<i+k&&nc>=na+1-i)||(na>=i+k&&nc>=na+1-i))){
res=0;
}
// cout<<na<<' '<<nc<<'\n';
na++;
}
if(p[f]=='B'){
if(!((nb<j)||(j<=nb&&nb<j+i&&na>=nb+1-j)||(nb>=j+i&&na>=nb+1-j))){
res=0;
}
nb++;
}
if(p[f]=='C'){
if(!((nc<k)||(k<=nc&&nc<k+j&&nb>=nc+1-k)||(nc>=k+j&&nb>=nc+1-k))){
res=0;
}
nc++;
}
}
ans=max(ans,res);
// if(res==1){
// cout<<i<<' '<<j<<' '<<k<<'\n';
// }
}
}
}
cout<<ans<<'\n';
}
return 0;
}
}
bool en;
signed main(){
#ifdef LOCAL_WRK
cerr<<"[Static Memory : "<<fixed<<((&st)-(&en))/1048576.0<<"MB]"<<endl;
#endif
return _wrk::main();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3620kb
input:
60 1 1 11 11 ABC 2 111 111 CABABC 3 1111 1111 CAABBCBAC 4 11111 11111 BACBBACBACAC 5 111111 111111 CABCCBBAABCCBAA 6 1111111 1111111 ABABABCACBCBCCACBA 7 11111111 11111111 BCAABACBBCBBABCCAACAC 8 111111111 111111111 CCBCBBBCAABCBCAAAAACBCBA 9 1111111111 1111111111 CCCCACABCBABAABCCAABABBCBBA 10 1111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
points 0.0 the max n you choose to answer is 0
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 0ms
memory: 3488kb
input:
60 3 1 11 11 ??? 2 111 111 ?????? 3 1111 1111 ????????? 4 11111 11111 ???????????? 5 111111 111111 ??????????????? 6 1111111 1111111 ?????????????????? 7 11111111 11111111 ????????????????????? 8 111111111 111111111 ???????????????????????? 9 1111111111 1111111111 ??????????????????????????? 10 1111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
points 0.0 the max n you choose to answer is 0
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%