oj.uz

Submission #613219

# Submission time Handle Problem Language Result Execution time Memory
613219 2022-07-30T04:02:51 Z czhang2718 HicCup (FXCUP4_hiccup) C++17
24 / 100
 312 ms 34876 KB 
#include "hiccup.h"
using namespace std;
#include "bits/stdc++.h"

const int N=1e6+1;
vector<int> adj[N];
int cnt[N];
int X;
bool bad;

void dfs(int x, int &c){
	c+=cnt[x];
	for(int i=adj[x].size()-1; i>=0; i--){
		int k=adj[x][i];
		dfs(k, c);
	}
	// cout << x << " have " << c << "\n";
	c-=X;
	if(x && c<0) bad=1;
}

int HicCup(std::string S) {
	int n = S.size();

	S='-'+S;
	stack<int> par;
	par.push(0);
	int prv=-1;
	for(int i=1; i<=n; i++){
		if(S[i]=='!'){
			if(prv==-1) return -1;
			cnt[prv]++;
			// cout << "cnt[" << prv << "]++\n";
			continue;
		}
		if(S[i]=='C'){
			if(par.size()<2) return -1;
			int p=par.top(); par.pop();
			adj[par.top()].push_back(p);
			// cout << "par " << p << " = " << par.top() << "\n";
			prv=p;
		}
		else{
			par.push(i);
		}
	}
	if(par.size()!=1) return -1;

	auto check=[&](int x){
		X=x;
		bad=0;
		int c=0;
		dfs(0, c);
		return !bad;
	};

	int x=0;
	for(int i=19; i>=0; i--){
		if(x+(1<<i)<n && check(x+(1<<i))) x+=(1<<i);
	}
	// check(2);
	if(!check(x)) return -1;
	return x;
}

// int main(){
// 	string s;
// 	cin >> s;
// 	cout << HicCup(s);
// }

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 18 ms 23692 KB Output is correct
3 Correct 15 ms 23800 KB Output is correct
4 Correct 17 ms 24220 KB Output is correct
5 Correct 312 ms 34852 KB Output is correct
6 Correct 19 ms 27700 KB Output is correct
7 Correct 21 ms 27604 KB Output is correct
8 Correct 300 ms 34860 KB Output is correct
9 Correct 309 ms 34876 KB Output is correct
10 Correct 19 ms 27604 KB Output is correct
11 Correct 16 ms 23764 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 18 ms 23692 KB Output is correct
3 Correct 15 ms 23800 KB Output is correct
4 Correct 17 ms 24220 KB Output is correct
5 Correct 312 ms 34852 KB Output is correct
6 Correct 19 ms 27700 KB Output is correct
7 Correct 21 ms 27604 KB Output is correct
8 Correct 300 ms 34860 KB Output is correct
9 Correct 309 ms 34876 KB Output is correct
10 Correct 19 ms 27604 KB Output is correct
11 Correct 16 ms 23764 KB Output is correct
12 Correct 23 ms 28360 KB Output is correct
13 Correct 20 ms 28424 KB Output is correct
14 Correct 20 ms 27588 KB Output is correct
15 Correct 12 ms 23720 KB Output is correct
16 Incorrect 30 ms 30612 KB Output isn't correct
17 Halted 0 ms 0 KB -