oj.uz

Submission #120819

# Submission time Handle Problem Language Result Execution time Memory
120819 2019-06-25T14:39:41 Z cvele Sajam (COCI18_sajam) C++14
90 / 90
 214 ms 2460 KB 
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

struct open {
  int x, on, t;
  open(int x, int on, int t) : x(x), on(on), t(t) {}
};

struct cmp {
  bool operator()(const open &a, const open &b) {
    if (a.on != b.on) {
      return a.on > b.on;
    }
    if (a.t != b.t) {
      return a.t < b.t;
    }
    if (a.x < b.x) {
      return a.x < b.x;
    }
    return 0;
  }
};

set <open, cmp> s;

int main() {
  int n, k;
  cin >> n >> k;
  char mat[n][n];
  int row[n], col[n];
  for (int i = 0; i < n; i++) {
    cin >> mat[i];
  }
  for (int i = 0; i < n; i++) {
    int on = 0;
    for (int j = 0; j < n; j++) {
      on += mat[i][j] == 'o';
    }
    row[i] = on;
    s.insert(open(i, on, 0));
  }
  for (int j = 0; j < n; j++) {
    int on = 0;
    for (int i = 0; i < n; i++) {
      on += (mat[i][j] == 'o');
    }
    col[j] = on;
    s.insert(open(j, on, 1));
  }
  bool usedrow[n], usedcol[n];
  memset(usedcol, 0, sizeof usedcol);
  memset(usedrow, 0, sizeof usedrow);
  while (!s.empty()) {
    open here = *s.begin(); s.erase(s.begin());
    if (here.t == 0) {
      usedrow[here.x] = 1;
    } else {
      usedcol[here.x] = 1;
    }
    if (here.on >= n - here.on) {
      if (here.t == 0) {
        int x = here.x;
        for (int y = 0; y < n; y++) {
          if (!usedcol[y]) {
            s.erase(open(y, col[y], 1));
            if (mat[x][y] == 'x') col[y]++;
            else col[y]--;
            s.insert(open(y, col[y], 1));
          }
          if (mat[x][y] == 'x') mat[x][y] = 'o';
          else mat[x][y] = 'x';
        }
      } else {
        int y = here.x;
        for (int x = 0; x < n; x++) {
          if (!usedrow[x]) {
            s.erase(open(x, row[x], 0));
            if (mat[x][y] == 'x') row[x]++;
            else row[x]--;
            s.insert(open(x, row[x], 0));
          }
          if (mat[x][y] == 'x') mat[x][y] = 'o';
          else mat[x][y] = 'x';
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      ans += (mat[i][j] == 'o');
    }
  }
  if (ans <= k) {
    cout << "DA" << endl;
  } else {
    cout << "NE" << endl;
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 31 ms 768 KB Output is correct
3 Correct 47 ms 952 KB Output is correct
4 Correct 145 ms 2296 KB Output is correct
5 Correct 49 ms 896 KB Output is correct
6 Correct 34 ms 512 KB Output is correct
7 Correct 53 ms 896 KB Output is correct
8 Correct 185 ms 2296 KB Output is correct
9 Correct 11 ms 384 KB Output is correct
10 Correct 197 ms 2268 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1536 KB Output is correct
2 Correct 135 ms 1764 KB Output is correct
3 Correct 91 ms 1404 KB Output is correct
4 Correct 78 ms 1272 KB Output is correct
5 Correct 164 ms 2132 KB Output is correct
6 Correct 56 ms 896 KB Output is correct
7 Correct 98 ms 1512 KB Output is correct
8 Correct 113 ms 1656 KB Output is correct
9 Correct 35 ms 640 KB Output is correct
10 Correct 214 ms 2424 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 1932 KB Output is correct
2 Correct 144 ms 1784 KB Output is correct
3 Correct 82 ms 1272 KB Output is correct
4 Correct 101 ms 1488 KB Output is correct
5 Correct 105 ms 1528 KB Output is correct
6 Correct 173 ms 2348 KB Output is correct
7 Correct 53 ms 768 KB Output is correct
8 Correct 98 ms 1528 KB Output is correct
9 Correct 123 ms 1536 KB Output is correct
10 Correct 210 ms 2296 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1280 KB Output is correct
2 Correct 88 ms 1280 KB Output is correct
3 Correct 186 ms 2368 KB Output is correct
4 Correct 53 ms 928 KB Output is correct
5 Correct 125 ms 1400 KB Output is correct
6 Correct 200 ms 2424 KB Output is correct
7 Correct 59 ms 1144 KB Output is correct
8 Correct 66 ms 1116 KB Output is correct
9 Correct 73 ms 1024 KB Output is correct
10 Correct 69 ms 1024 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 2460 KB Output is correct
2 Correct 191 ms 2296 KB Output is correct
3 Correct 161 ms 2168 KB Output is correct
4 Correct 93 ms 1504 KB Output is correct
5 Correct 95 ms 1528 KB Output is correct
6 Correct 138 ms 1536 KB Output is correct
7 Correct 60 ms 1024 KB Output is correct
8 Correct 163 ms 1912 KB Output is correct
9 Correct 89 ms 1272 KB Output is correct
10 Correct 213 ms 2168 KB Output is correct