Submission #171068

#	Time	Username	Problem	Language	Result	Execution time	Memory
171068		dndhk	parentrises (BOI18_parentrises)	C++14	100 / 100	246 ms	19408 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)

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];

int main(){
	scanf("%d%d", &P, &T);
	if(P==1){
		while(T--){
			bool tf = true;
			while(!vt.empty())	vt.pop_back();
			cin>>str;
			if(str[0]==')'){
				printf("impossible\n");
				continue;
			}
			vt.pb({1, 2});
			for(int i=1; i<str.size(); i++){
				pii prv = vt.back();
				if(str[i]=='('){
					prv.first++; prv.second+=2;
				}else{
					prv.first-=2; prv.second--;
				}
				if(prv.second<0){
					tf = false;
					break;
				}
				prv.first = max(prv.first, 0);
				vt.pb(prv);
			}
			if(vt.back().first!=0){
				tf = false;
			}
			if(!tf){
				printf("impossible\n");
			}else{
				int num1=0, num2=0;
				int n = 0;
				for(int i=str.size()-1; i>=0; i--){
					pii now = vt[i]; vt.pop_back();
					if(vt.empty()){
						if(n==2){
							ans.pb(3);
						}else{
							if(num1>0)	ans.pb(1);
							else	ans.pb(2);
						}
					}else{
						if(str[i]=='('){
							if(vt.back().first<=n-1 && n-1<=vt.back().second){
								if(num1<num2){
									ans.pb(2); num2--;
								}else{
									ans.pb(1); num1--;
								}
								n--;
							}else{
								ans.pb(3);
								num1--; num2--;
								n-=2;
							}
						}else{
							if(vt.back().first<=n+1 && n+1<=vt.back().second){
								if(num1>num2){
									ans.pb(2); num2++;
								}else{
									ans.pb(1); num1++;
								}
								n++;
							}else{
								ans.pb(3);
								num1++; num2++;
								n+=2;
							}
						}
					}
				}
				while(!ans.empty()){
					if(ans.back()==3){
						printf("G");
					}else if(ans.back()==2){
						printf("B");
					}else{
						printf("R");
					}
					ans.pop_back();
				}
				printf("\n");
			}
		}
	}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:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<str.size(); i++){
                 ~^~~~~~~~~~~
parentrises.cpp:71:10: warning: variable 'now' set but not used [-Wunused-but-set-variable]
      pii now = vt[i]; vt.pop_back();
          ^~~
parentrises.cpp:153:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(idx<query.size() && query[idx].first==n){
          ~~~^~~~~~~~~~~~~
parentrises.cpp:37: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:124: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