QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314436 | #8170. $N^a (\log N)^b$ | ucup-team2303# | WA | 11ms | 75548kb | C++17 | 2.6kb | 2024-01-25 17:56:16 | 2024-01-25 17:56:17 |
Judging History
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), 0};
}
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 << ' ' << res.y + res.z;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 75548kb
input:
N*log(N^2)*log(N)+N+log(N^1+N)^2*N
output:
1 2
result:
ok 2 tokens
Test #2:
score: -100
Wrong Answer
time: 11ms
memory: 74340kb
input:
N*log(log(N))
output:
1 0
result:
wrong answer 2nd words differ - expected: '1', found: '0'