QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#747195#5485. MazeMansuryaaprakasshWA 1ms3812kbC++203.4kb2024-11-14 16:33:182024-11-14 16:33:19

Judging History

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

  • [2024-11-14 16:33:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3812kb
  • [2024-11-14 16:33:18]
  • 提交

answer

#include <bits/stdc++.h>
// pbds
/*#include <ext/pb_ds/assoc_container.hpp> // Common file*/
/*#include <ext/pb_ds/tree_policy.hpp>*/
/**/
/*using namespace __gnu_pbds;*/
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...) 42
#endif
#define fast_io                                                                \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

/*typedef tree<int, null_type, less<int>, rb_tree_tag,*/
/*             tree_order_statistics_node_update>*/
/*    ordered_set;*/

bool vis[105][105];
bool cnt[105][105];
vector<string> v;
map<char, vector<pair<int, int>>> mp;
map<pair<int, int>, vector<char>> mpp;
map<char, ll> peop;
void dfs(int i, int j, int n, int m, char a) {
  if (i < 0 || j < 0 || i >= n || j >= m || vis[i][j] || v[i][j] == 'X')
    return;
  vis[i][j] = 1;
  if (v[i][j] == '.' || v[i][j] == a || v[i][j] == ' ') {
    ll key = i * 1000 + j;
    if (v[i][j] == '.') {
			peop[a]++;
			cnt[i][j] = 1;
      mpp[{i, j}].push_back(a);
    }
    if (mp.find(key) != mp.end()) {
      mp[a].push_back({i, j});
    } else {
      mp[a] = {{i, j}};
    }
    dfs(i - 1, j, n, m, a);
    dfs(i + 1, j, n, m, a);
    dfs(i, j - 1, n, m, a);
    dfs(i, j + 1, n, m, a);
  }
}

void solve() {
  ll n, m;
  cin >> n >> m;
  string a;
  v.resize(n);
  getline(cin, a);
  ll dot = 0;
  for (int i = 0; i < n; i++) {
    getline(cin, v[i]);
  }
  set<int> un;
  memset(cnt, 0, sizeof cnt);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      dot += (v[i][j] == '.');
      if (v[i][j] == 'X' || v[i][j] == '.' || v[i][j] == ' ')
        continue;
      memset(vis, 0, sizeof vis);
      dfs(i, j, n, m, v[i][j]);
    }
  }
  vector<pair<int, char>> vp;
  for (auto c : peop) {
    vp.push_back({c.second, c.first});
  }
  sort(rall(vp));
  vector<vector<bool>> check(n, vector<bool>(m, 0));
  ll score = 0;
  set<char> curr;
  for (auto x : mpp) {
    if (x.second.size() == 1 && curr.find(*x.second.begin()) == curr.end()) {
      if (!check[x.first.first][x.first.second]) {
        curr.insert(*x.second.begin());
        check[x.first.first][x.first.second] = 1;
      }
      continue;
    }
    char fuck = 'Z';
    char fc = 0;
    bool idd = 1;
    for (auto y : x.second) {
      if (curr.find(y) != curr.end()) {
        idd = 1;
        check[x.first.first][x.first.second] = 1;
        break;
      }
      if (peop[y] > fc) {
        fc = peop[y];
        fuck = y;
      }
    }
    if (idd && fuck != 'Z') {
      check[x.first.first][x.first.second] = 1;
      curr.insert(fuck);
    }
  }
  cout << curr.size() << " ";
  int nvis = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      nvis += cnt[i][j];
    }
  }
  cout << (dot - nvis) << "\n";
}

int main() {
  fast_io;
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("output.txt", "w", stderr);
#endif
  ll t = 1;
  /*cin >> t;*/
  while (t--) {
#ifdef LOCAL
    cout << "TEST CASE " << t + 1 << "\n";
#endif
    solve();
  }
#ifdef LOCAL
  cout << endl
       << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n\n";
#endif
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

10 20
XXXXXXXAXXXXXXXBXXXX
X.. ..X.X...... ...X
X.XXX...X.X.XXXXXX.X
X.X.XXXXX.X.X....X.X
X.X... ...X.X.XX.X.X
X.X.X.XXXXXXX.XX.X.X
X.X.X.X...X...X....X
X.X.X.XXXXXXX.XXXX.X
X...X.X X.. ..X..X.X
XXXXXXXDXXXXXXXXCXXX

output:

2 3

result:

ok 2 number(s): "2 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

3 5
XDRVX
X.X.X
XXXXX

output:

2 0

result:

ok 2 number(s): "2 0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

3 5
NAQXX
X X.X
XXXXX

output:

0 1

result:

ok 2 number(s): "0 1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

10 68
XXXXXXPXXXXXXXXCXXXXXXXXXXXXXXXXXXXXHXXXXXXXXXXXXXXIXXRXXXXXXXXXKXXX
X.XX..XXXX.X.X.XXXXXX..XXXXX.X.X......X ......X.X.. X.....XXX..  X.X
X X.X.XXX.. X..X..X ..X..XX.XX.XXXXX.X....X.X.X.XXXX.X. X..X.X.....X
X.X..XX .XX..X....X.XX.X..XXX....X.X. .X....X.X .XX.X...X.XXX.. X..X
X.X..X..XXXXXX .. ...

output:

4 116

result:

ok 2 number(s): "4 116"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

7 4
WIRX
VX.S
OXXN
XX E
K..B
T.XQ
CMDL

output:

2 0

result:

ok 2 number(s): "2 0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

14 65
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X...... .XXX..X.X. ..XXX.XXX XX.X.X.XX .X.XXX..X.XX..XXXX....X .X
XXX..X.XXXXXXX..X.X....XX...XXX..XXX..XX....X...X.......X..X.XXXX
X.X.X......XXX .....XX. ...XX...X.X.XXX...X.....X.X.XX.XX ..X X X
X...........X.....X X...XXX.XX...

output:

1 318

result:

ok 2 number(s): "1 318"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

42 20
XAXXXXXXXXXXXXXXXXNX
X..X.XX.XX....XX.XXX
XX.XXX  X....XXX...V
X......XX...XXXXX..X
X....XX....X.XX....X
JX.XX XXX.XX..XX.XXX
X. ..XXX....XXX...XX
XX.... .XXX.XX..X.XX
X.X.....XX.X..X .X.X
X.X. ....XX.....XX.X
X X..X...X.XXXXXX..X
X.......XX.X..X.XXXX
X..XX...XX......XXXX
XX.XX..X ...X...XX.X
...

output:

3 258

result:

ok 2 number(s): "3 258"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

45 86
XXXXXXXXXXXXXXXXXXXXXXXXXXEXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXX.X..XXXX.. XX.XX.X.X..XX....XX..X.X.X.XX.....X.X.X. ..X..XX.XX.XX.XX..X..X....XXX.X
XX...XX...XXX.XX.XXXX. XX....X. XXX....XXXXX...X.X.XXX.......XXX.X..XX...X.X..X..XX.XX
X XX...X.XX..XX. X...X..... .X..X...

output:

1 1791

result:

ok 2 number(s): "1 1791"

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3640kb

input:

35 47
XXXXXXXXXOXXXXXXXXHSXXXXXXXXNXXXXXXXXXXMXXXXXXX
X.X.XXX..XXXX.....X .  X........X  X..XX.XX..XQ
X.XXXX XX..X.....X..X....XX. XX..X..X.XX..XXX.X
X.XX..X....XX.XXX. X..XXX.XX.X..X.X.X.XX.X.X..X
X.X...XXX.X..X..XX X..X.. XXX..X XX.XXX..X.X..P
XXX.X..X... XX.......X XX.X X...X..  ..XX.X...X
X.X.XX...

output:

7 463

result:

wrong answer 1st numbers differ - expected: '6', found: '7'