QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#643885#8776. Not Another Constructive!ainta#WA 5ms10132kbC++204.1kb2024-10-16 05:49:062024-10-16 05:49:06

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 05:49:06]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:10132kb
  • [2024-10-16 05:49:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}


struct modinfo{uint mod,root;};
template<modinfo const&ref>
struct modular{
	static constexpr uint const &mod=ref.mod;
	static modular root(){return modular(ref.root);}
	uint v;
	//modular(initializer_list<uint>ls):v(*ls.bg){}
	modular(ll vv=0){s(vv%mod+mod);}
	modular& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	modular operator-()const{return modular()-*this;}
	modular& operator+=(const modular&rhs){return s(v+rhs.v);}
	modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);}
	modular&operator*=(const modular&rhs){
		v=ull(v)*rhs.v%mod;
		return *this;
	}
	modular&operator/=(const modular&rhs){return *this*=rhs.inv();}
	modular operator+(const modular&rhs)const{return modular(*this)+=rhs;}
	modular operator-(const modular&rhs)const{return modular(*this)-=rhs;}
	modular operator*(const modular&rhs)const{return modular(*this)*=rhs;}
	modular operator/(const modular&rhs)const{return modular(*this)/=rhs;}
	modular pow(int n)const{
		modular res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modular inv()const{return pow(mod-2);}
	/*modular inv()const{
		int x,y;
		int g=extgcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return modular(x);
	}*/
	friend modular operator+(int x,const modular&y){
		return modular(x)+y;
	}
	friend modular operator-(int x,const modular&y){
		return modular(x)-y;
	}
	friend modular operator*(int x,const modular&y){
		return modular(x)*y;
	}
	friend modular operator/(int x,const modular&y){
		return modular(x)/y;
	}
	friend ostream& operator<<(ostream&os,const modular&m){
		return os<<m.v;
	}
	friend istream& operator>>(istream&is,modular&m){
		ll x;is>>x;
		m=modular(x);
		return is;
	}
	bool operator<(const modular&r)const{return v<r.v;}
	bool operator==(const modular&r)const{return v==r.v;}
	bool operator!=(const modular&r)const{return v!=r.v;}
	explicit operator bool()const{
		return v;
	}
};
extern constexpr modinfo base{998244353,0};
using mint=modular<base>;
using pdi = pair<double, int>;
using ld = long double;
#define N_  200010

int n, m;
bitset<2501>D[41][41][401];
char p[42], res[42];
void Solve(){
	scanf("%d%d",&n,&m);
	scanf("%s",p);
	D[0][0][0][0]=1;
	rep(i,n){
		rng(j,0,i){
			rng(k,0,(i/2)*((i+1)/2)){
				if(p[i]=='N'||p[i]=='?') D[i+1][j+1][k] |= D[i][j][k];
				if(p[i]=='A'||p[i]=='?') D[i+1][j][k+j] |= D[i][j][k];
				if(p[i]=='C'||p[i]=='?') D[i+1][j][k] |= (D[i][j][k] << k);
				if(p[i]!='N'&&p[i]!='A'&&p[i]!='C') D[i+1][j][k] |= D[i][j][k];
			}
		}
	}
	int x=-1,y,z;
	rng(i,0,n){
		rng(j,0,400){
			if(D[n][i][j][m]){
				x=i,y=j,z=m;
			}
		}
	}
	if(x==-1){
		puts("-1");
		return;
	}
	per(i,n){
		if((p[i]=='N' || p[i]=='?') && x>=1 && D[i][x-1][y][z] == 1){
			res[i]='N';
			x--;
			continue;
		}
		if((p[i]=='A' || p[i]=='?') && y>=x && D[i][x][y-x][z] == 1){
			res[i]='A';
			x--;
			continue;
		}
		if((p[i]=='C' || p[i]=='?') && z>=y && D[i][x][y][z-y] == 1){
			res[i]='C';
			x--;
			continue;
		}
		if(p[i]=='?') res[i]='Z';
		else res[i]=p[i];
	}
	res[n]=0;
	printf("%s\n",res);
}

int main(){
	int TC=1;
	//scanf("%d",&TC);
	while(TC--){
		Solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 10132kb

input:

22 2
N??A??????C???????????

output:

NZZACNNNNNCNNNNNNNNNNN

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 6560kb

input:

18 0
COUNTINGSATELLITES

output:

COUNTINGSATELLITES

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

2 1
??

output:

-1

result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

1 0
?

output:

N

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

1 0
N

output:

N

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

1 0
X

output:

X

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

1 1
?

output:

-1

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1 1
N

output:

-1

result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

1 1
X

output:

-1

result:

ok correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

2 0
??

output:

NN

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

2 0
N?

output:

NN

result:

ok correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

2 0
?C

output:

AC

result:

ok correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

2 1
N?

output:

-1

result:

ok correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

2 1
?C

output:

-1

result:

ok correct

Test #15:

score: -100
Wrong Answer
time: 0ms
memory: 3784kb

input:

3 1
???

output:

ZZC

result:

wrong answer incorrect number of subsequences: 0