oj.uz

Submission #74108

# Submission time Handle Problem Language Result Execution time Memory
74108 2018-08-30T06:05:11 Z zscoder parentrises (BOI18_parentrises) C++17
50 / 100
 55 ms 12392 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int ans[1111111];

bool solve(string &s)
{
	int n=s.length();
	for(int i=0;i<n;i++) ans[i]=0;
	int ptr = 0;
	stack<int> S;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='(')
		{
			S.push(i);
		}
		else
		{
			if(!S.empty())
			{
				int u=S.top();
				ans[i]|=1; ans[u]|=1; S.pop();
			}
			else
			{
				while(ptr<i&&(s[ptr]!='('||ans[ptr]>=3)) ptr++;
				if(ptr>=i) return 0;
				ans[ptr]|=2; ans[i]|=2; 
			}
		}
	}
	ptr=n-1;
	for(int i=n-1;i>=0;i--)
	{
		if(s[i]==')'||ans[i]>0) continue;
		while(ptr>i&&(s[ptr]!=')'||ans[ptr]>=3)) ptr--;
		if(ptr<=i) return 0;
		ans[i]|=2; ans[ptr]|=2;
	}
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int type; cin>>type;
	int t; cin>>t;
	while(t--)
	{
		if(type==1)
		{
			string s; cin>>s; 
			bool tmp = solve(s);
			if(!tmp) 
			{
				cout<<"impossible\n"; 
				continue;
			}
			for(int i=0;i<s.length();i++)
			{
				if(ans[i]==1) cout<<"B";
				else if(ans[i]==2) cout<<"R";
				else cout<<"G";
			}
			cout<<'\n';		
		}
		else
		{
			int n; cin>>n;
			
		}
	}
}

Compilation message

parentrises.cpp: In function 'int main()':
parentrises.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<s.length();i++)
                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 608 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 772 KB Output is correct
5 Correct 2 ms 772 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 772 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 2 ms 772 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 2 ms 772 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 772 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 2 ms 772 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 2 ms 772 KB Output is correct
11 Correct 2 ms 772 KB Output is correct
12 Correct 2 ms 880 KB Output is correct
13 Correct 2 ms 880 KB Output is correct
14 Correct 3 ms 880 KB Output is correct
15 Correct 2 ms 880 KB Output is correct
16 Correct 6 ms 1088 KB Output is correct
17 Correct 7 ms 1716 KB Output is correct
18 Correct 6 ms 1716 KB Output is correct
19 Correct 6 ms 1716 KB Output is correct
20 Correct 7 ms 2012 KB Output is correct
21 Correct 36 ms 3008 KB Output is correct
22 Correct 53 ms 9280 KB Output is correct
23 Correct 38 ms 9280 KB Output is correct
24 Correct 44 ms 9280 KB Output is correct
25 Correct 55 ms 12392 KB Output is correct

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12392 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12392 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12392 KB Unexpected end of file - int32 expected