QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94040 | #6115. Blocks and Expressions | sinbad# | WA | 2ms | 3500kb | C++ | 5.4kb | 2023-04-05 07:56:32 | 2023-04-05 07:56:34 |
Judging History
answer
// #define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
constexpr inline int lg2(int64 x) { return x == 0 ? -1 : sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
constexpr inline int p2ceil(int64 x) { return 1 << (lg2(x - 1) + 1); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
inline void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
inline void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
inline int mod(int x) { return x >= MOD ? x - MOD : x; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
struct Node {
int x;
Node* ch[2];
};
const int N = 1e3 + 10;
Node pool[N];
Node* last;
Node* new_node(int x) {
Node* ret = last++;
ret->x = x;
ret->ch[0] = ret->ch[1] = nullptr;
return ret;
}
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) cin >> s[i];
last = pool;
auto get = [&](char c) {
int x;
if (isdigit(c)) {
x = c - '0';
} else if (c == '+') {
x = 10;
} else if (c == '-') {
x = 11;
} else {
x = 12;
}
return new_node(x);
};
auto P = vect<Node*>(nullptr, n, m);
auto vis = vect<bool>(0, n, m);
Node* rt;
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < m; ++j) {
if (s[i][j] != '.') {
auto* p = get(s[i][j]);
rt = P[i][j] = p;
if (i + 1 < n && p->x >= 10) {
int ll, rr;
for (ll = j - 1; ll >= 0 && s[i + 1][ll] == '.'; --ll);
for (rr = j + 1; rr < m && s[i + 1][rr] == '.'; ++rr);
if (ll >= 0 && rr < m && !vis[i + 1][ll] && !vis[i + 1][rr]) {
vis[i + 1][ll] = vis[i + 1][rr] = 1;
p->ch[0] = P[i + 1][ll];
p->ch[1] = P[i + 1][rr];
}
}
}
}
}
trace(rt->x);
function<int64(Node*)> solve =
[&](Node* p) -> int64 {
if (p->x >= 0 && p->x < 10) return p->x;
int ret;
if (p->x == 10) {
ret = solve(p->ch[0]) + solve(p->ch[1]);
} else if (p->x == 11) {
ret = solve(p->ch[0]) - solve(p->ch[1]);
} else {
ret = solve(p->ch[0]) * solve(p->ch[1]);
}
return ret;
};
cout << solve(rt) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3432kb
input:
1 1 5
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
2 3 .-. 9.2
output:
7
result:
ok 1 number(s): "7"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
4 9 ...*..... .-.....+. 9.4..*..5 ....7.2..
output:
95
result:
ok 1 number(s): "95"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
9 35 ...............................+... ...........*.....................*. .+.....................+........8.6 5........+...........-...+......... .......*..1........*..0.0....*..... ...+....5....*......8......+..9.... ..5..+......2..+..........4.9...... ....5.9.......7..*................. ..........
output:
34489
result:
ok 1 number(s): "34489"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
9 31 .....................+......... .................+.....+....... ...-...............*..2..-..... .+.....*..........7.3...7....+. 4.1..-.........-...........*..5 ....0.5......*..2.........8.8.. ...........*..8................ .........+..2.................. ........2.5....................
output:
516
result:
ok 1 number(s): "516"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
7 29 ...........+................. .......-.................*... ...*.....-.......+.........+. .-...*..0.2....*...*......8.2 5.7.2.1......-..1.2..-....... ............8.3.....8..*..... ......................3.1....
output:
148
result:
ok 1 number(s): "148"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
5 13 ...........-. .....+......8 .*.....*..... 0..+..0..+... ..8.2...0.6..
output:
-8
result:
ok 1 number(s): "-8"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
7 21 .......+............. .-.......*........... 4....-..5..........+. ...+..1....*........6 ..8.0.....2....+..... .............+...+... ............0.8.9.1..
output:
207
result:
ok 1 number(s): "207"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
5 13 .........*... ...-.......+. .*.....+..2.4 9.5..+..0.... ....6.1......
output:
228
result:
ok 1 number(s): "228"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3372kb
input:
7 29 .................-........... ...........*.......-......... .......+.......+..7........-. .*.......*...-..1........+..1 0..-....6.0.7.6........-..1.. ..5..*...............-..1.... ....9.0.............4.8......
output:
-12
result:
ok 1 number(s): "-12"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
9 37 .....................*............... ...................*.......+......... ...........-........5..-...........+. .........+.....+......3..+.....*....5 .+........7..-...+......1.4..-...-... 2......*....9.3.3.1.........2.8.2.2.. .....+..8............................ ...+..6.........................
output:
1185
result:
ok 1 number(s): "1185"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3380kb
input:
9 23 .-..................... 3..+................... ..3..............-..... .....+...............+. ....9..+...........-..8 ......4......*....9.5.. ...........+...+....... .........+..7.3.1...... ........4.9............
output:
-81
result:
ok 1 number(s): "-81"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
12 37 .................................+... ...............................*...+. ...........................-....5.0.1 .........................+...*....... ...................+......6.5.9...... ...+.................*............... .*.....+............7..*............. 4.4..-...........*....1.8......
output:
371
result:
ok 1 number(s): "371"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
3 5 ...+. .*..2 9.3..
output:
29
result:
ok 1 number(s): "29"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
6 15 .*............. 0....*......... ...+.....*..... ..7.0..-...+... ......5.8.5..-. ............7.5
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3424kb
input:
5 11 .........+. .....+....7 .-.....+... 8..-..1.6.. ..3.4......
output:
23
result:
ok 1 number(s): "23"
Test #17:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
8 23 .+..................... 4....................+. .......-..............4 .....*.....+........... ...+..3..-.........-... ..5.9...4.1....-....5.. .............-...+..... ............5.1.8.3....
output:
59
result:
ok 1 number(s): "59"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
9 23 .*..................... 9....................+. ...................*..6 .......-............1.. .....+.....*........... ...+..8..+...-......... ..6.0...1.1.4....+..... ...............*..9.... ..............1.0......
output:
270
result:
ok 1 number(s): "270"
Test #19:
score: 0
Accepted
time: 2ms
memory: 3468kb
input:
2 3 .-. 8.4
output:
4
result:
ok 1 number(s): "4"
Test #20:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
5 13 ...-......... .*.......+... 0.4....+...-. .....+..6.8.1 ....4.8......
output:
-25
result:
ok 1 number(s): "-25"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
6 33 .................+............... .....+.....................*..... ...+.......+...........-.....+... .-..4..*.......*.....-...-..7..-. 0.9...4..+...-..7..*..1.9.1...4.6 ........9.4.7.5...2.8............
output:
96
result:
ok 1 number(s): "96"
Test #22:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
7 29 ...............+............. .........+.............+..... .-.........-.........*.....-. 5..*......7..*.....-..4..-..9 ..5..+......3.7..+..9...6.6.. ....1..+........0.0.......... ......2.1....................
output:
-74
result:
ok 1 number(s): "-74"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3380kb
input:
6 17 ...*............. .-.........-..... 0.1......+.....-. .....*....0..-..4 ....0..-....9.9.. ......0.6........
output:
-4
result:
ok 1 number(s): "-4"
Test #24:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
6 33 ...............*................. .......+.................*....... .+.......+...........+.....*..... 7..*....6..-.......*...-..8..+... ..3..-....0..-...+..3.8.4...2..-. ....7.4.....7.2.7.8...........6.8
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
6 27 .............*............. .....+...............+..... .-.....*.......+.........+. 2..+..8....*..4..-.....+..0 ..9.3....*..0...1..*..7.5.. ........3.0.......6.3......
output:
10
result:
ok 1 number(s): "10"
Test #26:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
6 25 .........+............... .......*.........-....... .*......8....+.........+. 6....*.....*...-.....-..4 ...*..3...1.1.7.4..*..6.. ..8.7.............1.1....
output:
8069
result:
ok 1 number(s): "8069"
Test #27:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
6 15 .....+......... .+.....+....... 6..-..3..+..... ..7.7...4..-... ..........1..-. ............8.1
output:
7
result:
ok 1 number(s): "7"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
10 37 .*................................... 5......*............................. ...*.......-......................... ..4..-...-...........-............... ....7.8.0.6........*...............+. ...............-....1..+............0 .............*...+....8......*....... ............0.7.0.4......*.....
output:
-3120
result:
ok 1 number(s): "-3120"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
8 37 .......-............................. .*.................+................. 4....+...........*...*............... ...-..7......-....0.2............+... ..3.3....-.....-.............-.....-. ........9..-..9.6........*.....+..3.5 ..........8.8..........-...*..3.1.... ......................7.6.3.4...
output:
16
result:
ok 1 number(s): "16"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
8 37 .....................-............... .................*.................-. ...+...............+.........-......3 .*.....+..........4.5......-.....+... 0.4..*.........+.......*....0..*..8.. ....8.1....*....6.....1..*....4.8.... .........+...+..........7.1.......... ........6.5.7.4.................
output:
1251
result:
ok 1 number(s): "1251"
Test #31:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
8 37 .........................-........... ...........+.................*....... .........*.......+.........*.......-. .+........8..+.......-....2.0..+....0 0..*........8..-...*...-......6..+... ..3..-........0.1.2.9.8.1.......3.4.. ....0..+............................. ......1.5.......................
output:
-126
result:
ok 1 number(s): "-126"
Test #32:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
8 37 .....................+............... ...........-.............*........... .........-...+.........+...........+. .*........6.7..+......5.4....+......9 8......+......0..*.........-.....*... .....-..6.......0..*......4.9..-..2.. ...*..5...........9.5.........9.8.... ..0.9...........................
output:
49
result:
ok 1 number(s): "49"
Test #33:
score: 0
Accepted
time: 2ms
memory: 3424kb
input:
10 37 ...................................-. .............................*......5 ...+...........................-..... .*.....................+......4..*... 6.4....-.................-......1.0.. .....+.......+..........2..+......... ....4.7..-.......*........1.4........ ........2..-...+.....-.........
output:
-29
result:
ok 1 number(s): "-29"
Test #34:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
10 37 ...............................+..... .........................-.......-... .....................-.....+....1..+. .+.....................-..7..-....2.9 6..............*......0.7...7.8...... .......*...........*................. ...+.....+.......+..0................ ..5..+..8..+....1.1............
output:
-3
result:
ok 1 number(s): "-3"
Test #35:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
12 37 ...*................................. .-.................................+. 1.3..............................+..9 .............................*....3.. .......+.......................-..... .....*.....*..................9.6.... ....0.0..*.....*..................... ........5.3..*.....-...........
output:
-384
result:
ok 1 number(s): "-384"
Test #36:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
10 37 ...............................*..... ...........................*.....-... .-...........................-..4..+. 9....-......................2.8...7.6 ...-.................*............... ..8.6....-.............+............. .......+.......-......5..-........... ......8.7..*.......*....7.1....
output:
19980
result:
ok 1 number(s): "19980"
Test #37:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
12 37 .....+............................... ...*...............................+. .-..2..+............................7 0.3...2........................*..... ...........................*.....*... .......................+.....+..3.9.. .........-...............-..3.7...... ........1......*........1.6....
output:
-311037
result:
ok 1 number(s): "-311037"
Test #38:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
7 37 .................-................... ...........+.............-........... .........*...-.........*.......-..... ...+......5.8..-.....+..5..-.......-. .-.....-......4.2..*..0...3..*...-..0 9.7..+..0.........9.9.......8.5.6.1.. ....8.1..............................
output:
-386
result:
ok 1 number(s): "-386"
Test #39:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
7 37 .....................+............... .........+.....................-..... .+.............-.............*.....*. 7..*.......+.....-.....+......3..+..6 ..2....-..5..-..9..+..2..-......8.2.. .....+..8...6.4...2.8...4..-......... ....3.8...................3.5........
output:
-15
result:
ok 1 number(s): "-15"
Test #40:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
7 37 ...................*................. .............*.................-..... .........*.....-...........*.....+... .......-...-..8..+.....+.....+..9..+. ...-....6.9.0...0.3..+...-..4.9...1.6 .-...*..............5.1.5.3.......... 6.7.6.3..............................
output:
-99000
result:
ok 1 number(s): "-99000"
Test #41:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
7 37 ...............+..................... ...*.................*............... .-.........+.......-.......*......... 9.0....+.....+...-..5..*.....-....... .....+...-..5.1.6.3...4..-..3....*... ....8.7.4.4.............4.5....-...+. ..............................1.9.0.7
output:
661
result:
ok 1 number(s): "661"
Test #42:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
8 37 .....................*............... .......+.................*........... .....-...-.............*.....-....... .*....6.7..-..........3.6..+.....-... 9..+......7....*..........4.1..-...*. ..8.0........-...*............1.4.9.1 ............0.5.8..-................. ..................1.9...........
output:
118116
result:
ok 1 number(s): "118116"
Test #43:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
1 1 7
output:
7
result:
ok 1 number(s): "7"
Test #44:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
1 1 8
output:
8
result:
ok 1 number(s): "8"
Test #45:
score: 0
Accepted
time: 2ms
memory: 3440kb
input:
1 1 7
output:
7
result:
ok 1 number(s): "7"
Test #46:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
1 1 8
output:
8
result:
ok 1 number(s): "8"
Test #47:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
1 1 3
output:
3
result:
ok 1 number(s): "3"
Test #48:
score: -100
Wrong Answer
time: 0ms
memory: 3444kb
input:
8 37 .......................*............. ...............*.............*....... .............*.......*.....*...*..... .......*......9..*....7..*..8.9..*... .....*...*......9..*....9.9.....9..*. .*....8.7..*......8.9.............9.7 9..*......9.9........................ ..7.8...........................
output:
-1373138944
result:
wrong answer 1st numbers differ - expected: '308616905200472064', found: '-1373138944'