QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314438 | #8170. $N^a (\log N)^b$ | ucup-team2303# | WA | 20ms | 82444kb | C++17 | 2.6kb | 2024-01-25 17:58:04 | 2024-01-25 17:58:05 |
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), 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'