Submission #995591

#	Time	Username	Problem	Language	Result	Execution time	Memory
995591		lovrot	Homework (CEOI22_homework)	C++17	100 / 100	131 ms	139276 KiB

Main

#include <cstdio> 
#include <algorithm> 

using namespace std; 

const int N = 7e6 + 10;

struct node {
	int a, l, r; 
	node() : a(1), l(0), r(0) {}
	node(int a, int l, int r) : a(a), l(l), r(r) {}
}; 

node min(node a, node b) { 
	return node(a.a + b.a, min(a.l, b.l), a.r + b.r + 1);
}

node max(node a, node b) { 
	return node(a.a + b.a, a.l + b.l + 1, min(a.r, b.r));
}

int n;
char C[N];
int ind = 0; 

node dfs(int i) {
	if(C[i] == '?') { 
		ind = i;
		return node();
	} else if(C[i + 2] == 'x') { 
		node a = dfs(i + 4); 
		node b = dfs(ind + 2);
		ind += 1;
//		printf("max %d %d %d %d %d %d\n", a.a, a.l, a.r, b.a, b.l, b.r);
		return max(a, b);
	}
	node a = dfs(i + 4); 
	node b = dfs(ind + 2);
	ind += 1;
//	printf("min %d %d %d %d %d %d\n", a.a, a.l, a.r, b.a, b.l, b.r);
	return min(a, b);
}

int main() {
	scanf("%s%n ", C, &n); 
	node res = dfs(0);
	printf("%d\n", res.a - res.l - res.r);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%s%n ", C, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34