답안 #949996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949996	2024-03-20T02:46:09 Z	Abito	Chorus (JOI23_chorus)	C++17	16 / 100	40 ms	32240 KB

chorus

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=21,M=2e6;
int dis[M],n,k;
char a[N];
void bfs(int s){
    dis[s]=0;
    queue<int> q;q.push(s);
    while (!q.empty()){
        int x=q.front();q.pop();
        for (int i=0;i<2*n-1;i++){
            if ((x&(1<<i)) && (x&(1<<(i+1)))) continue;
            if (!(x&(1<<i)) && !(x&(1<<(i+1)))) continue;
            int y=x;
            y^=(1<<i);
            y^=(1<<(i+1));
            if (dis[y]==-1) dis[y]=dis[x]+1,q.push(y);
        }
    }return;
}
bool check(int s){
    int x=0,y=0;
    bool vis[2*n]={0};
    for (int i=2*n-1;i>=0;i--){
        if (s&(1<<i)){
            x++;
            continue;
        }
        if (vis[i]) continue;
        y++;
        for (int j=i;j>=0 && x;j--){
            if (s&(1<<j)) continue;
            if (vis[j]) continue;
            vis[j]=1;x--;
        }
    }
    return y<=k && !x;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    memset(dis,-1,sizeof(dis));
    cin>>n>>k;int mask=0;
    for (int i=0;i<2*n;i++){
        cin>>a[i];
        if (a[i]=='B') mask|=(1<<i);
    }
    bfs(mask);
    int ans=INT_MAX;
    for (int i=0;i<M;i++){
        if (dis[i]==-1) continue;
        if (check(i)) ans=min(ans,dis[i]);
    }cout<<ans<<endl;
    return 0;
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	4 ms	15964 KB	Output is correct
3	Correct	4 ms	15964 KB	Output is correct
4	Correct	40 ms	15964 KB	Output is correct
5	Correct	4 ms	15964 KB	Output is correct
6	Correct	5 ms	16112 KB	Output is correct
7	Correct	37 ms	15964 KB	Output is correct
8	Correct	38 ms	15964 KB	Output is correct
9	Correct	37 ms	15964 KB	Output is correct
10	Correct	38 ms	15964 KB	Output is correct
11	Correct	39 ms	16160 KB	Output is correct
12	Correct	37 ms	15960 KB	Output is correct
13	Correct	37 ms	16220 KB	Output is correct
14	Correct	38 ms	15964 KB	Output is correct
15	Correct	37 ms	15964 KB	Output is correct
16	Correct	36 ms	16220 KB	Output is correct

Subtask #2

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	4 ms	15964 KB	Output is correct
3	Correct	4 ms	15964 KB	Output is correct
4	Correct	40 ms	15964 KB	Output is correct
5	Correct	4 ms	15964 KB	Output is correct
6	Correct	5 ms	16112 KB	Output is correct
7	Correct	37 ms	15964 KB	Output is correct
8	Correct	38 ms	15964 KB	Output is correct
9	Correct	37 ms	15964 KB	Output is correct
10	Correct	38 ms	15964 KB	Output is correct
11	Correct	39 ms	16160 KB	Output is correct
12	Correct	37 ms	15960 KB	Output is correct
13	Correct	37 ms	16220 KB	Output is correct
14	Correct	38 ms	15964 KB	Output is correct
15	Correct	37 ms	15964 KB	Output is correct
16	Correct	36 ms	16220 KB	Output is correct
17	Runtime error	15 ms	32240 KB	Execution killed with signal 11
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	4 ms	15964 KB	Output is correct
3	Correct	4 ms	15964 KB	Output is correct
4	Correct	40 ms	15964 KB	Output is correct
5	Correct	4 ms	15964 KB	Output is correct
6	Correct	5 ms	16112 KB	Output is correct
7	Correct	37 ms	15964 KB	Output is correct
8	Correct	38 ms	15964 KB	Output is correct
9	Correct	37 ms	15964 KB	Output is correct
10	Correct	38 ms	15964 KB	Output is correct
11	Correct	39 ms	16160 KB	Output is correct
12	Correct	37 ms	15960 KB	Output is correct
13	Correct	37 ms	16220 KB	Output is correct
14	Correct	38 ms	15964 KB	Output is correct
15	Correct	37 ms	15964 KB	Output is correct
16	Correct	36 ms	16220 KB	Output is correct
17	Runtime error	15 ms	32240 KB	Execution killed with signal 11
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	4 ms	15964 KB	Output is correct
3	Correct	4 ms	15964 KB	Output is correct
4	Correct	40 ms	15964 KB	Output is correct
5	Correct	4 ms	15964 KB	Output is correct
6	Correct	5 ms	16112 KB	Output is correct
7	Correct	37 ms	15964 KB	Output is correct
8	Correct	38 ms	15964 KB	Output is correct
9	Correct	37 ms	15964 KB	Output is correct
10	Correct	38 ms	15964 KB	Output is correct
11	Correct	39 ms	16160 KB	Output is correct
12	Correct	37 ms	15960 KB	Output is correct
13	Correct	37 ms	16220 KB	Output is correct
14	Correct	38 ms	15964 KB	Output is correct
15	Correct	37 ms	15964 KB	Output is correct
16	Correct	36 ms	16220 KB	Output is correct
17	Runtime error	15 ms	32240 KB	Execution killed with signal 11
18	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	4 ms	15964 KB	Output is correct
3	Correct	4 ms	15964 KB	Output is correct
4	Correct	40 ms	15964 KB	Output is correct
5	Correct	4 ms	15964 KB	Output is correct
6	Correct	5 ms	16112 KB	Output is correct
7	Correct	37 ms	15964 KB	Output is correct
8	Correct	38 ms	15964 KB	Output is correct
9	Correct	37 ms	15964 KB	Output is correct
10	Correct	38 ms	15964 KB	Output is correct
11	Correct	39 ms	16160 KB	Output is correct
12	Correct	37 ms	15960 KB	Output is correct
13	Correct	37 ms	16220 KB	Output is correct
14	Correct	38 ms	15964 KB	Output is correct
15	Correct	37 ms	15964 KB	Output is correct
16	Correct	36 ms	16220 KB	Output is correct
17	Runtime error	15 ms	32240 KB	Execution killed with signal 11
18	Halted	0 ms	0 KB	-