QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94040#6115. Blocks and Expressionssinbad#WA 2ms3500kbC++5.4kb2023-04-05 07:56:322023-04-05 07:56:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 07:56:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3500kb
  • [2023-04-05 07:56:32]
  • 提交

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'