oj.uz

답안 #1090647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090647 2024-09-18T14:56:52 Z noyancanturk parentrises (BOI18_parentrises) C++17
100 / 100
 99 ms 106712 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=301;
const int mod=1e9+7;

int sum(int i,int j){
  if(i+j<mod)return i+j;
  return i+j-mod;
}

void solve1(){
  string s;
  cin>>s;
  int n=s.size();
  int ty[n]{};
  int haveemp=0;
  vector<int>pools[2];
  for(int i=0;i<n;i++){
    if(s[i]=='('){
      haveemp++;
    }else if(1<haveemp){
      pools[0].pb(i);
      haveemp-=2;
    }else if(haveemp){
      pools[1].pb(i);
      ty[i]=1;
      haveemp=0;
    }else if(pools[0].size()){
      int toconvert=pools[0].back();
      pools[0].pop_back();
      ty[toconvert]=ty[i]=1;
      pools[1].pb(i);
      pools[1].pb(toconvert);
    }else if(pools[1].size()){
      int toconvert=pools[1].back();
      pools[1].pop_back();
      ty[i]=2;
      ty[toconvert]=3;
    }else{
      cout<<"impossible\n";
      return;
    }
  }
  if(haveemp){
    cout<<"impossible\n";
    return;
  }
  int needgreen=0,needred=0,needblue=0;
  string ans=string(n,' ');
  for(int i=n-1;0<=i;i--){
    if(s[i]=='('){
      if(needgreen){
        ans[i]='G';
        needgreen--;
      }else if(needred){
        ans[i]='R';
        needred--;
      }else if(needblue){
        ans[i]='B';
        needblue--;
      }
    }else if(ty[i]==0){
      ans[i]='G';
      needred++,needblue++;
    }else if(ty[i]==1){
      ans[i]='G';
      needgreen++;
    }else if(ty[i]==2){
      ans[i]='B';
    }else{
      ans[i]='R';
      needgreen++;
    }
  }
  cout<<ans<<"\n"; 
}

int dp[lim][lim][lim];

void solve2(){
  int n;
  cin>>n;
  int ans=0;
  for(int i=0;i<lim;i++)
    ans=sum(ans,dp[n][0][i]);
  cout<<ans<<"\n";
}

int main(){
  #ifdef Local
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
  #endif
  int _;
  cin>>_;
  if(_==1){
    int t;
    cin>>t;
    while(t--)solve1();
  }else{
    dp[0][0][0]=1;
    for(int i=1;i<lim;i++){
      for(int j=0;j<lim;j++){
        for(int k=0;k<lim;k++){
          dp[i][j][k]=sum(j?dp[i-1][j-1][k]:0,2<k&&j+2<lim?dp[i-1][j+2][k-3]:0);
        }
      }
      for(int k=0;k<lim;k++){
        dp[i][0][k]=sum(dp[i][0][k],sum(k?dp[i-1][1][k-1]:0,k+1<lim?dp[i-1][0][k+1]:0));
      }
    }
    int t;
    cin>>t;
    while(t--)solve2();
  }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 448 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 12 ms 460 KB Output is correct
17 Correct 3 ms 1496 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 3 ms 1016 KB Output is correct
20 Correct 3 ms 1496 KB Output is correct
21 Correct 99 ms 2024 KB Output is correct
22 Correct 33 ms 10048 KB Output is correct
23 Correct 22 ms 2948 KB Output is correct
24 Correct 29 ms 5664 KB Output is correct
25 Correct 30 ms 10296 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 106712 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 106712 KB Output is correct
2 Correct 70 ms 106576 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 106712 KB Output is correct
2 Correct 70 ms 106576 KB Output is correct
3 Correct 81 ms 106696 KB Output is correct