QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733520#8776. Not Another Constructive!nice333TL 1000ms251756kbC++231.7kb2024-11-10 19:36:332024-11-10 19:36:33

Judging History

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

  • [2024-11-10 19:36:33]
  • 评测
  • 测评结果:TL
  • 用时:1000ms
  • 内存:251756kb
  • [2024-11-10 19:36:33]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
using namespace std;
void solve() {
    int n,k;cin>>n>>k;
    string s;cin>>s;s="#"+s;
    vector<map<array<int,3>,pair<char,array<int,3>>>>f(n+1,map<array<int,3>,pair<char,array<int,3>>>());
    f[0][{0,0,0}]={'#',{0,0,0}};
    for(int i=1;i<=n;i++){
        for(auto [o,oo]:f[i-1]){
            auto [a1,a2,a3]=o;
            if(s[i]=='N')f[i][{a1+1,a2,a3}]={'N',o};
            else if(s[i]=='A')f[i][{a1,a1+a2,a3}]={'A',o};
            else if(s[i]=='C'){
                if(a2+a3<=k)
                    f[i][{a1,a2,a2+a3}]={'C',o};
            }
            else if(s[i]=='?'){
                if(a1+1<=k)
                    f[i][{a1+1,a2,a3}]={'N',o};
                if(a1+a2<=k)
                    f[i][{a1,a1+a2,a3}]={'A',o};
                if(a2+a3<=k)
                    f[i][{a1,a2,a2+a3}]={'C',o};
                f[i][o]={'E',o};
            }
            else f[i][o]={s[i],o};
        }
    }
    char cur='#';
    array<int,3>last;
    for(auto [o,oo]:f[n]){
        auto [a1,a2,a3]=o;
        if(a3==k){
            cur=oo.first;
            last=oo.second;
            break;
        }
    }
    if(cur=='#'){
        cout<<"-1\n";
        return;
    }
    s[n]=cur;
    for(int i=n-1;i>0;i--){
        auto [o,oo]=f[i][last];
        s[i]=o;
        last=oo;
    }
    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: 0ms
memory: 3552kb

input:

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

output:

NEEACEEEEECEEEEEEEEEEE

result:

ok correct

Test #2:

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

input:

18 0
COUNTINGSATELLITES

output:

COUNTINGSATELLITES

result:

ok correct

Test #3:

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

input:

2 1
??

output:

-1

result:

ok correct

Test #4:

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

input:

1 0
?

output:

E

result:

ok correct

Test #5:

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

input:

1 0
N

output:

N

result:

ok correct

Test #6:

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

input:

1 0
X

output:

X

result:

ok correct

Test #7:

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

input:

1 1
?

output:

-1

result:

ok correct

Test #8:

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

input:

1 1
N

output:

-1

result:

ok correct

Test #9:

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

input:

1 1
X

output:

-1

result:

ok correct

Test #10:

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

input:

2 0
??

output:

EE

result:

ok correct

Test #11:

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

input:

2 0
N?

output:

NE

result:

ok correct

Test #12:

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

input:

2 0
?C

output:

EC

result:

ok correct

Test #13:

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

input:

2 1
N?

output:

-1

result:

ok correct

Test #14:

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

input:

2 1
?C

output:

-1

result:

ok correct

Test #15:

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

input:

3 1
???

output:

NAC

result:

ok correct

Test #16:

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

input:

3 1
N??

output:

NAC

result:

ok correct

Test #17:

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

input:

3 1
?A?

output:

NAC

result:

ok correct

Test #18:

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

input:

3 1
??C

output:

NAC

result:

ok correct

Test #19:

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

input:

3 1
NA?

output:

NAC

result:

ok correct

Test #20:

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

input:

3 1
N?C

output:

NAC

result:

ok correct

Test #21:

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

input:

3 1
?AC

output:

NAC

result:

ok correct

Test #22:

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

input:

4 1
????

output:

NACE

result:

ok correct

Test #23:

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

input:

4 1
X???

output:

XNAC

result:

ok correct

Test #24:

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

input:

4 1
???Z

output:

NACZ

result:

ok correct

Test #25:

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

input:

4 1
?AA?

output:

-1

result:

ok correct

Test #26:

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

input:

4 1
N???

output:

NACE

result:

ok correct

Test #27:

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

input:

4 1
?N??

output:

ENAC

result:

ok correct

Test #28:

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

input:

4 1
??N?

output:

NANC

result:

ok correct

Test #29:

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

input:

4 1
???N

output:

NACN

result:

ok correct

Test #30:

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

input:

4 1
A???

output:

ANAC

result:

ok correct

Test #31:

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

input:

4 1
?A??

output:

NACE

result:

ok correct

Test #32:

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

input:

4 1
??A?

output:

NEAC

result:

ok correct

Test #33:

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

input:

4 1
???A

output:

NACA

result:

ok correct

Test #34:

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

input:

4 1
C???

output:

CNAC

result:

ok correct

Test #35:

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

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: 3556kb

input:

4 1
???C

output:

NAEC

result:

ok correct

Test #38:

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

input:

5 4
?????

output:

NAACC

result:

ok correct

Test #39:

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

input:

6 14
??????

output:

-1

result:

ok correct

Test #40:

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

input:

7 14
???????

output:

-1

result:

ok correct

Test #41:

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

input:

8 43
????????

output:

-1

result:

ok correct

Test #42:

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

input:

9 55
?????????

output:

-1

result:

ok correct

Test #43:

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

input:

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

output:

-1

result:

ok correct

Test #44:

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

input:

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

output:

-1

result:

ok correct

Test #45:

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

input:

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

output:

NACCCCEEEEEE

result:

ok correct

Test #46:

score: 0
Accepted
time: 5ms
memory: 5076kb

input:

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

output:

-1

result:

ok correct

Test #47:

score: 0
Accepted
time: 8ms
memory: 6072kb

input:

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

output:

NNNANAAACACCCC

result:

ok correct

Test #48:

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

input:

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

output:

NACACCCCCCCEEEE

result:

ok correct

Test #49:

score: 0
Accepted
time: 16ms
memory: 9880kb

input:

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

output:

-1

result:

ok correct

Test #50:

score: 0
Accepted
time: 32ms
memory: 13160kb

input:

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

output:

-1

result:

ok correct

Test #51:

score: 0
Accepted
time: 50ms
memory: 18240kb

input:

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

output:

-1

result:

ok correct

Test #52:

score: 0
Accepted
time: 30ms
memory: 12592kb

input:

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

output:

NACAACCCCCCCCCCCCCE

result:

ok correct

Test #53:

score: 0
Accepted
time: 109ms
memory: 34048kb

input:

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

output:

-1

result:

ok correct

Test #54:

score: 0
Accepted
time: 146ms
memory: 46988kb

input:

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

output:

-1

result:

ok correct

Test #55:

score: 0
Accepted
time: 218ms
memory: 64036kb

input:

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

output:

-1

result:

ok correct

Test #56:

score: 0
Accepted
time: 316ms
memory: 86412kb

input:

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

output:

-1

result:

ok correct

Test #57:

score: 0
Accepted
time: 438ms
memory: 115984kb

input:

24 1445
????????????????????????

output:

-1

result:

ok correct

Test #58:

score: 0
Accepted
time: 577ms
memory: 154096kb

input:

25 1331
?????????????????????????

output:

-1

result:

ok correct

Test #59:

score: 0
Accepted
time: 768ms
memory: 201372kb

input:

26 459
??????????????????????????

output:

NNNANAAAAAAAAAAAACCCCCCCCC

result:

ok correct

Test #60:

score: 0
Accepted
time: 1000ms
memory: 251756kb

input:

27 398
???????????????????????????

output:

NNANAAAACAAAAAACCCCCCCCCCCC

result:

ok correct

Test #61:

score: -100
Time Limit Exceeded

input:

28 274
????????????????????????????

output:


result: