QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314438#8170. $N^a (\log N)^b$ucup-team2303#WA 20ms82444kbC++172.6kb2024-01-25 17:58:042024-01-25 17:58:05

Judging History

你现在查看的是最新测评结果

  • [2024-01-25 17:58:05]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:82444kb
  • [2024-01-25 17:58:04]
  • 提交

answer

// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) {rep(i, 0, siz(n) - 1) cout << n[i] << " \n"[i == siz(n) - 1];}

const int N = 1e6;
string s;
int ch[N + 5];
vi add[N + 5], mul[N + 5], pw[N + 5], q;
struct pii {int x, y, z;};

pii max(pii n, pii m) {
	if(n.x > m.x) return n;
	if(n.x < m.x) return m;

	if(n.y > m.y) return n;
	if(n.y < m.y) return m;

	if(n.z > m.z) return n;
	return m;
}
pii A(pii n, pii m) {
	return max(n, m);
}
pii M(pii n, pii m) {
	return pii {n.x + m.x, n.y + m.y, n.z || m.z};
}
pii P(pii n, int m) {
	return pii {n.x * m, n.y * m, n.z};
}
pii log(pii n) {
	return pii {0, min(1ll, n.x), n.y || n.z};
}

int find(vi &n, int l, int r) {
	auto x = lower_bound(n.begin(), n.end(), l);
	if(x == n.end()) return -1;
	return (*x) <= r ? *x : -1;
}
int get(int l, int r) {
	int res = 0;
	rep(i, l, r) {
		assert(s[i] >= '0' && s[i] <= '9');
		res = res * 10 + s[i] - '0';
	}
	return res;
}
pii solve(int l, int r, int o) {
	// cout << l << ' ' << r << ' ' << s.substr(l, r - l + 1) << endl;
	if(l == r) {
		assert(s[l] == 'N');
		return pii {1, 0, 0};
	}
	int x = find(add[o], l, r);
	if(x != -1) {
		// cout << l << ' ' << x << ' ' << r << endl;
		return A(solve(l, x - 1, o), solve(x + 1, r, o));
	}

	x = find(mul[o], l, r);
	if(x != -1) return M(solve(l, x - 1, o), solve(x + 1, r, o));

	x = find(pw[o], l, r);
	if(x != -1) {
		// cout << "#@!@!@" << endl;
		return P(solve(l, x - 1, o), get(x + 1, r));
	}

	if(r - l + 1 >= 3 && s.substr(l, 3) == "log") return log(solve(l + 3, r, o));

	if(s[l] == '(' && s[r] == ')') {
		assert(ch[l] == r);
		return solve(l + 1, r - 1, o + 1);
	}

	assert(0);
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s;
	rep(i, 0, siz(s) - 1) {
		if(s[i] == '(') q.PB(i);
		else if(s[i] == ')') {
			ch[q.back()] = i, ch[i] = q.back();
			q.pop_back();
		}
		else if(s[i] == '*') mul[siz(q)].PB(i);
		else if(s[i] == '+') add[siz(q)].PB(i);
		else if(s[i] == '^') pw[siz(q)].PB(i);
	}
	auto res = solve(0, siz(s) - 1, 0);
	cout << res.x << ' ' << max(res.y, res.z);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 20ms
memory: 74656kb

input:

N*log(N^2)*log(N)+N+log(N^1+N)^2*N

output:

1 2

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 8ms
memory: 74180kb

input:

N*log(log(N))

output:

1 1

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 7ms
memory: 75232kb

input:

(((N))*N^234567890+N^2)

output:

234567891 0

result:

ok 2 tokens

Test #4:

score: 0
Accepted
time: 12ms
memory: 80000kb

input:

log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)...

output:

0 1

result:

ok 2 tokens

Test #5:

score: 0
Accepted
time: 11ms
memory: 79492kb

input:

log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)...

output:

0 14285

result:

ok 2 tokens

Test #6:

score: 0
Accepted
time: 7ms
memory: 82444kb

input:

log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(log(...

output:

0 1

result:

ok 2 tokens

Test #7:

score: 0
Accepted
time: 16ms
memory: 75100kb

input:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

0 1

result:

ok 2 tokens

Test #8:

score: -100
Wrong Answer
time: 13ms
memory: 76004kb

input:

log(log(N^39187693)^548521633+log(log(N*N^2+N*N^71962925)+log(N*N+N)*log(N+N)+log((log(log(N)^8))*log(log(N*N*N))))*log((N+log(N)*N+N*log(N)^958544341))^978444210)+log((log(N)^573073630)*log(log(N)^857299008)*(N+N^3+log(N))*log(N)+log(log(N^5943+((N*N)*N^3371597)+N*N*(N)*N^3732602)^195356379)^910014...

output:

0 706139982

result:

wrong answer 2nd words differ - expected: '706139983', found: '706139982'