QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733007#8776. Not Another Constructive!aYi_7#TL 872ms141880kbC++173.5kb2024-11-10 16:50:392024-11-10 16:50:40

Judging History

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

  • [2024-11-10 16:50:40]
  • 评测
  • 测评结果:TL
  • 用时:872ms
  • 内存:141880kb
  • [2024-11-10 16:50:39]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5;
void solve() {
    int n,k;cin>>n>>k;
    string s;cin>>s;s="#"+s;
    vector<vector<set<array<int,3>>>>f(n+1,vector<set<array<int,3>>>(4));
    f[0][0].insert({0,0,0});f[0][1].insert({0,0,0});f[0][2].insert({0,0,0});f[0][3].insert({0,0,0});
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            for(auto [a1,a2,a3]:f[i-1][j]){
                if(s[i]=='N')f[i][0].insert({a1+1,a2,a3});
                else if(s[i]=='A')f[i][1].insert({a1,a1+a2,a3});
                else if(s[i]=='C')f[i][2].insert({a1,a2,a2+a3});
                else if(s[i]=='?'){
                    f[i][0].insert({a1+1,a2,a3});
                    f[i][1].insert({a1,a1+a2,a3});
                    f[i][2].insert({a1,a2,a2+a3});
                    f[i][3].insert({a1,a2,a3});
                }
                else f[i][3].insert({a1,a2,a3});
            }
        }
    }
    char last='#';
    int l1,l2,l3;
    if(s[n]=='N'){
        for(auto [a1,a2,a3]:f[n][0])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='N';
            }
    }
    else if(s[n]=='A'){
        for(auto [a1,a2,a3]:f[n][1])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='A';
            }
    }
    else if(s[n]=='C'){
        for(auto [a1,a2,a3]:f[n][2])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='C';
            }
    }
    else if(s[n]=='?'){
        for(auto [a1,a2,a3]:f[n][0])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='N';
            }
        for(auto [a1,a2,a3]:f[n][1])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='A';
            }
        for(auto [a1,a2,a3]:f[n][2])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='C';
            }
        for(auto [a1,a2,a3]:f[n][3])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='?';
            }
    }
    else{
        for(auto [a1,a2,a3]:f[n][3])
            if(a3==k){
                l1=a1;l2=a2;l3=a3;
                last='?';
            }
    }
    if(last=='#'){
        cout<<"-1\n";
        return;
    }
    if(s[n]=='?')s[n]=last;
    if(s[n]=='?')s[n]='E';
    //cout<<l1<<" "<<l2<<" "<<l3<<"\n";
    for(int i=n-1;i>0;i--){
        bool flag=0;
        for(int j=0;j<4;j++){
            if(flag)break;
            for(auto [a1,a2,a3]:f[i][j]){
                if(flag)break;
                int n1=a1,n2=a2,n3=a3;
                if(last=='N')n1++;
                else if(last=='A')n2+=n1;
                else if(last=='C')n3+=n2;
                if(n1==l1&&n2==l2&&n3==l3){
                    l1=a1;l2=a2;l3=a3;
                    if(j==0)last='N';
                    if(j==1)last='A';
                    if(j==2)last='C';
                    if(j==3)last='?';
                    flag=1;
                }
            }
        }
        if(s[i]=='?')s[i]=last;
        if(s[i]=='?')s[i]='E';
        //cout<<l1<<" "<<l2<<" "<<l3<<"\n";
    }
    s.erase(s.begin());
    cout<<s<<"\n";
}

/**
22 2
N??A??????C???????????
18 0
COUNTINGSATELLITES
2 1
??
 * **/
signed main() {
//    std::ios::sync_with_stdio(false);
//    std::cin.tie(nullptr);
    int t = 1;
    //std::cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 583ms
memory: 100916kb

input:

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

output:

NCNANNNNNNCNNNNNNNNNNE

result:

ok correct

Test #2:

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

input:

18 0
COUNTINGSATELLITES

output:

COUNTINGSATELLITES

result:

ok correct

Test #3:

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

input:

2 1
??

output:

-1

result:

ok correct

Test #4:

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

input:

1 0
?

output:

E

result:

ok correct

Test #5:

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

input:

1 0
N

output:

N

result:

ok correct

Test #6:

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

input:

1 0
X

output:

X

result:

ok correct

Test #7:

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

input:

1 1
?

output:

-1

result:

ok correct

Test #8:

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

input:

1 1
N

output:

-1

result:

ok correct

Test #9:

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

input:

1 1
X

output:

-1

result:

ok correct

Test #10:

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

input:

2 0
??

output:

NE

result:

ok correct

Test #11:

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

input:

2 0
N?

output:

NE

result:

ok correct

Test #12:

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

input:

2 0
?C

output:

NC

result:

ok correct

Test #13:

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

input:

2 1
N?

output:

-1

result:

ok correct

Test #14:

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

input:

2 1
?C

output:

-1

result:

ok correct

Test #15:

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

input:

3 1
???

output:

NAC

result:

ok correct

Test #16:

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

input:

3 1
N??

output:

NAC

result:

ok correct

Test #17:

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

input:

3 1
?A?

output:

NAC

result:

ok correct

Test #18:

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

input:

3 1
??C

output:

NAC

result:

ok correct

Test #19:

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

input:

3 1
NA?

output:

NAC

result:

ok correct

Test #20:

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

input:

3 1
N?C

output:

NAC

result:

ok correct

Test #21:

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

input:

3 1
?AC

output:

NAC

result:

ok correct

Test #22:

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

input:

4 1
????

output:

NACE

result:

ok correct

Test #23:

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

input:

4 1
X???

output:

XNAC

result:

ok correct

Test #24:

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

input:

4 1
???Z

output:

NACZ

result:

ok correct

Test #25:

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

input:

4 1
?AA?

output:

-1

result:

ok correct

Test #26:

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

input:

4 1
N???

output:

NACE

result:

ok correct

Test #27:

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

input:

4 1
?N??

output:

ANAC

result:

ok correct

Test #28:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

4 1
??N?

output:

NANC

result:

ok correct

Test #29:

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

input:

4 1
???N

output:

NACN

result:

ok correct

Test #30:

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

input:

4 1
A???

output:

ANAC

result:

ok correct

Test #31:

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

input:

4 1
?A??

output:

NACE

result:

ok correct

Test #32:

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

input:

4 1
??A?

output:

ANAC

result:

ok correct

Test #33:

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

input:

4 1
???A

output:

NACA

result:

ok correct

Test #34:

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

input:

4 1
C???

output:

CNAC

result:

ok correct

Test #35:

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

input:

4 1
?C??

output:

NCAC

result:

ok correct

Test #36:

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

input:

4 1
??C?

output:

NACE

result:

ok correct

Test #37:

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

input:

4 1
???C

output:

NANC

result:

ok correct

Test #38:

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

input:

5 4
?????

output:

NNAAC

result:

ok correct

Test #39:

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

input:

6 14
??????

output:

-1

result:

ok correct

Test #40:

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

input:

7 14
???????

output:

-1

result:

ok correct

Test #41:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

8 43
????????

output:

-1

result:

ok correct

Test #42:

score: 0
Accepted
time: 1ms
memory: 4052kb

input:

9 55
?????????

output:

-1

result:

ok correct

Test #43:

score: 0
Accepted
time: 2ms
memory: 4032kb

input:

10 112
??????????

output:

-1

result:

ok correct

Test #44:

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

input:

11 110
???????????

output:

-1

result:

ok correct

Test #45:

score: 0
Accepted
time: 6ms
memory: 5148kb

input:

12 4
????????????

output:

NNNNACNNNNNE

result:

ok correct

Test #46:

score: 0
Accepted
time: 10ms
memory: 6284kb

input:

13 193
?????????????

output:

-1

result:

ok correct

Test #47:

score: 0
Accepted
time: 19ms
memory: 8336kb

input:

14 91
??????????????

output:

NNNNANAAACACCC

result:

ok correct

Test #48:

score: 0
Accepted
time: 35ms
memory: 11468kb

input:

15 15
???????????????

output:

NNNNNNNANACNNNE

result:

ok correct

Test #49:

score: 0
Accepted
time: 54ms
memory: 16336kb

input:

16 261
????????????????

output:

-1

result:

ok correct

Test #50:

score: 0
Accepted
time: 94ms
memory: 23636kb

input:

17 514
?????????????????

output:

-1

result:

ok correct

Test #51:

score: 0
Accepted
time: 150ms
memory: 34348kb

input:

18 678
??????????????????

output:

-1

result:

ok correct

Test #52:

score: 0
Accepted
time: 250ms
memory: 49716kb

input:

19 40
???????????????????

output:

NNNNNNNNNNNNNAANACE

result:

ok correct

Test #53:

score: 0
Accepted
time: 386ms
memory: 71276kb

input:

20 1019
????????????????????

output:

-1

result:

ok correct

Test #54:

score: 0
Accepted
time: 588ms
memory: 101240kb

input:

21 1218
?????????????????????

output:

-1

result:

ok correct

Test #55:

score: 0
Accepted
time: 872ms
memory: 141880kb

input:

22 1348
??????????????????????

output:

-1

result:

ok correct

Test #56:

score: -100
Time Limit Exceeded

input:

23 476
???????????????????????

output:


result: