Submission #227865

#	Time	Username	Problem	Language	Result	Execution time	Memory
227865		quocnguyen1012	parentrises (BOI18_parentrises)	C++14	100 / 100	217 ms	19160 KiB

parentrises

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)
#define ii pair<int, int>
#define fi first
#define se second
#define eb emplace_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const ll MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 300;

int P, T, N;
string str;
vector<pii> vt;
vector<int> ans;

vector<pii> query;
ll answer[MAX_N+1];
ll dp[2][MAX_N+1][MAX_N*3+1];

void solve(void)
{
  string str; cin >> str;
  int n = str.size();
  vector<ii> sum;
  if(str[0] == ')'){
    cout << "impossible\n";
    return;
  }
  bool ok = true;
  sum.eb(1, 2);
  for(int i = 1; i < n; ++i){
    auto now = sum.back();
    if(str[i] == '('){
      now.fi++; now.se += 2;
    }
    else{
      now.fi -= 2; now.se--;
    }
    if(now.se < 0){
      ok = false;
      break;
    }
    now.fi = max(now.fi, 0);
    sum.eb(now);
  }
  if(sum.back().fi != 0)
    ok = false;
  if(!ok){
    cout << "impossible\n";
    return;
  }
  //for(auto it : sum) cerr << it.fi << ' ' << it.se << '\n';
  int suf = 0, num1 = 0, num2 = 0;
  vector<int> ans;
  for(int i = n - 1; i >= 0; --i){
    //cerr << suf << ' ';
    if(i == 0){
      if(suf == 2){
        ans.eb(3);
      }
      else{
        if(num1 > 0) ans.eb(1);
        else ans.eb(2);
      }
    }
    else{
      auto need = sum[i - 1];
      if(str[i] == '('){
        if(need.fi <= suf - 1 && suf - 1 <= need.se){
          suf--;
          if(num2 > num1){
            ans.eb(2); --num2;
          }
          else{
            ans.eb(1); --num1;
          }
        }
        else{
          suf -= 2;
          ans.eb(3);
          --num1; --num2;
        }
      }
      else{
        if(need.fi <= suf + 1 && suf + 1 <= need.se){
          ++suf;
          if(num2 > num1){
            ans.eb(1); ++num1;
          }
          else{
            ans.eb(2); ++num2;
          }
        }
        else{
          suf += 2;
          ans.eb(3);
          ++num1; ++num2;
        }
      }
    }
  }
  for(int i = n - 1; i >= 0; --i){
    if(ans[i] == 3){
      cout << 'G';
    }
    else if(ans[i] == 1){
      cout << 'R';
    }
    else{
      cout << 'B';
    }
  }
  cout << '\n';
}

int main(){
	#ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
	scanf("%d%d", &P, &T);
	if(P==1){
		while(T--){
			solve();
		}
	}else{
		for(int i=0; i<T; i++){
			scanf("%d", &N);
			query.pb({N, i});
		}
		sort(query.begin(), query.end());
		dp[0][0][0] = 1LL;
		int idx = 0;
		for(int n=1; n<=MAX_N; n++){
			for(int i=0; i<n; i++){
				for(int j=0; j<=2*MAX_N; j++){
					dp[1][i+1][j+1] = (dp[1][i+1][j+1] + dp[0][i][j]) % MOD;
					if(i*2>=n-i)	dp[1][i][max(0, j-2)] = (dp[1][i][max(0, j-2)] + dp[0][i][j]) % MOD;
				}
			}
			TEST cout<<n<<endl;
			for(int i=0; i<=n; i++){
				for(int j=0; j<=2*MAX_N; j++){
					dp[0][i][j] = dp[1][i][j];
					dp[1][i][j] = 0LL;
					TEST{
						if(dp[0][i][j]!=0){
							cout<<i<<" "<<j<<" "<<dp[0][i][j]<<endl;
						}
					}
				}
			}
			ll sum = 0;
			for(int j=0; j<=n; j++){
				sum = (sum + dp[0][j][0]) % MOD;
			}
			while(idx<query.size() && query[idx].first==n){
				answer[query[idx].second] = sum;
				idx++;
			}
		}
		for(int i=0; i<T; i++){
			printf("%lld\n", answer[i]);
		}
	}
	return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:177:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(idx<query.size() && query[idx].first==n){
          ~~~^~~~~~~~~~~~~
parentrises.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &P, &T);
  ~~~~~^~~~~~~~~~~~~~~~
parentrises.cpp:148:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &N);
    ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28