#2327634

Solution for 2512: Ononokomachi's Edit War by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 2    
00.08 sec    3192 KB    256 lines     4084 bytes    2017-05-20 05:05
#ifndef _WIN32
#include<iostream>
#endif 

#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long LL;
#define FOR(i,bg,ed) for(int i = (bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
struct cww {
	cww() {
		ios::sync_with_stdio(false);
		cin.tie(0);
	}
}star;
template<typename T>
istream & operator>> (istream &is, vector<T>&v) {
	for (auto &it : v)is >> it;
	return is;
}
#define fi first
#define se second
#define ALL(x) (x).begin(),(x).end()
#define NG {ok=false;return 0;}
typedef pair<LL, LL> P;
typedef vector<LL> V;
const int INF = 1e7;

int N;
int id = 0;
string s;
bool ok;
int no() {
	return (int)s.size() <= id;
}

int parse_num() {
	int val = 0, sz = 0, lzero = 0;
	if (no())NG
	if (!isdigit(s[id]))NG;
	if (s[id] == '0')lzero++;
	while (!no()) {
		if (isdigit(s[id])) {
			val *= 10;
			val += s[id++] - '0';
			sz++;
		}
		else break;
	}
	if (lzero == 1)NG;
	return val;
}
int parse_mul(int v);
int parse_plus_minus(int v);
int parse_and(int v);
int parse_xor(int v);
int parse_or(int v);
int parse();

int parse() {
	if (no()) NG
	if (s[id] == '(') {
		id++;
		int ret = parse();
		if (s[id] == ')') {
			id++;
			return parse_or(ret);
		}
		else NG
	}
	else {
		int val = parse_num();
		return parse_or(val);
	}
}
int parse_mul(int v) {
	int all = 1;
	while (1) {
		if (no())return all * v;
		switch (s[id]) {
		case '+':
		case '-':
		case '&':
		case '^':
		case '|':
		case ')': return all * v;
		case '*':
		{
			all *= v;
			id++;
			if (no()) NG;
			if (s[id] == '(')v = parse();
			else v = parse_num();
			break;
		}
		default: NG
		}
	}
}

int parse_plus_minus(int v) {
	int all = 0;
	int prev = 1;
	while (1) {
		if (no())return all +prev * v;
		switch (s[id]) {
		case '&':
		case '^':
		case '|':
		case ')': return all + prev * v;
		case '+':
		{
			all += prev*v;
			id++;
			if (no()) NG;
			if (s[id] == '(')v = parse();
			else v = parse_num();
			prev = 1;
			break;
		}
		case '-':
		{
			all += prev*v;
			id++;
			if (no()) NG;
			if (s[id] == '(')v = parse();
			else v = parse_num();
			prev = -1;
			break;
		}
		case '*':
			v = parse_mul(v); break;
		default: NG
		}
	}
}

int parse_and(int v) {
	int all = -1;
	while (1) {
		if (no())return all & v;
		switch (s[id]) {
		case '^':
		case '|':
		case ')': return all & v;
		case '&':
		{
			all &= v;
			id++;
			if (no()) NG
				if (s[id] == '(')v = parse();
				else v = parse_num();
				break;
		}
		case '*':
		case '-':
		case '+':
			v = parse_plus_minus(v); break;
		default: NG
		}
	}
}

int parse_xor(int v) {
	int all = 0;
	while (1) {
		if (no())return all ^ v;
		switch (s[id]) {
		case '|':
		case ')': return all ^ v;
		case '^':
		{
			all ^= v;
			id++;
			if (no()) NG
			if (s[id] == '(')v = parse();
			else v = parse_num();
			break;
		}
		case '*':
		case '-':
		case '+':
		case '&':
			v = parse_and(v); break;
		default: NG
		}
	}
}
int parse_or(int v) {
	int all = 0;
	while (1) {
		if (no())return all|v;
		switch (s[id]) {
		case ')': return all | v;
		case '|': 
		{
			all |= v;
			id++;
			if (no()) NG
			if (s[id] == '(')v = parse();
			else v = parse_num();
			break;
		}
		case '^':
		case '&':
		case '+':
		case '-':
		case '*':v = parse_xor(v); break;
		default: NG
		}
	}
}
string t = "+-*&^|0123456789";
int minmax(string now,int depth,int v) {
	//cout << depth << " " << now << endl;
	s = now;

	if (depth == 0) {
		id = 0; return v*parse();
	}
	int res = -1e8;
	int n = now.size();
	REP(i, n+1) for(auto c:t){
		s = now; ok = true; id = 0;
		s.insert(i,1, c);
		int nxt = parse();
		//if(ok)cout << s <<" "<<-nxt<<endl;
		if (ok)res = max(res, -minmax(s, depth - 1, v));
	}
	REP(i, n)if(now[i]!='('&&now[i]!=')') {
		s = now; ok = true; id = 0;
		s.erase(i,1);
		if (s.size() > 0u);
		int nxt =parse();
		//if (ok)cout << s << " " << v*nxt << endl;
		if (ok)res = max(res, -minmax(s, depth - 1, v));

	}
	return res;

}

int main() {
	while (cin >> N >> s, s != "#") {
		ok = true;
		
		if(N%2)cout << minmax(s,1,-1) << endl;
		else cout << minmax(s, 2, 1) << endl;
	}
	return 0;
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 4/4 C++14 CPU: 00.08 sec Memory: 3192 KB Length: 4084 B 2017-05-20 05:05 2017-05-20 05:05
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.08 sec 3172 KB
Case #2: : Accepted 00.08 sec 3172 KB
Case #3: : Accepted 00.08 sec 3192 KB
Case #4: : Accepted 00.08 sec 3160 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags