oj.uz

Submission #613252

# Submission time Handle Problem Language Result Execution time Memory
613252 2022-07-30T04:11:00 Z czhang2718 HicCup (FXCUP4_hiccup) C++17
24 / 100
 418 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];
	// if(X==2) cout << x << " c " << c << "\n";
	if(x) c-=X;
	if(x && c<0) bad=1;
	for(int i=adj[x].size()-1; i>=0; i--){
		int k=adj[x][i];
		dfs(k, c);
	}
}

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]++;
			continue;
		}
		if(S[i]=='C'){
			if(par.size()<2) return -1;
			int p=par.top(); par.pop();
			prv=p;
			adj[par.top()].push_back(p);
		}
		else{
			par.push(i);
		}
	}
	// for(int i=0; i<=n; i++){
	// 	if(cnt[i]) cout << "cnt[" << i << "] " << cnt[i] << "\n";
	// }
	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 15 ms 23720 KB Output is correct
2 Correct 16 ms 23780 KB Output is correct
3 Correct 18 ms 23764 KB Output is correct
4 Correct 24 ms 24224 KB Output is correct
5 Correct 368 ms 34848 KB Output is correct
6 Correct 24 ms 27604 KB Output is correct
7 Correct 25 ms 27648 KB Output is correct
8 Correct 340 ms 34864 KB Output is correct
9 Correct 418 ms 34876 KB Output is correct
10 Correct 21 ms 27604 KB Output is correct
11 Correct 18 ms 23800 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23720 KB Output is correct
2 Correct 16 ms 23780 KB Output is correct
3 Correct 18 ms 23764 KB Output is correct
4 Correct 24 ms 24224 KB Output is correct
5 Correct 368 ms 34848 KB Output is correct
6 Correct 24 ms 27604 KB Output is correct
7 Correct 25 ms 27648 KB Output is correct
8 Correct 340 ms 34864 KB Output is correct
9 Correct 418 ms 34876 KB Output is correct
10 Correct 21 ms 27604 KB Output is correct
11 Correct 18 ms 23800 KB Output is correct
12 Correct 27 ms 28288 KB Output is correct
13 Correct 23 ms 28460 KB Output is correct
14 Correct 20 ms 27640 KB Output is correct
15 Correct 17 ms 23764 KB Output is correct
16 Incorrect 27 ms 30592 KB Output isn't correct
17 Halted 0 ms 0 KB -