oj.uz

Submission #888929

# Submission time Handle Problem Language Result Execution time Memory
888929 2023-12-18T12:03:49 Z nguyentunglam Seats (IOI18_seats) C++17
5 / 100
 4000 ms 40516 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const int N = 1e6 + 10, M = 1010;

int r[N], c[N];
int h, w;

bool a[M][M];

void give_initial_chart(int _h, int _w, vector<int> _r, vector<int> _c) {
//   for(int i = 0; i < _h * _w; i++) cout << _r[i] << " " << _c[i] << endl;

   h = _h; w = _w;
   for(int i = 0; i < h * w; i++) r[i] = _r[i] + 1, c[i] = _c[i] + 1;

//   for(int i = 0; i < h * w; i++) cout << r[i] << " " << c[i] << endl;
}

int calc (int x, int y) {
  return a[x][y] + a[x][y + 1] + a[x + 1][y] + a[x + 1][y + 1];
}

int swap_seats(int x, int y) {
  swap(r[x], r[y]);
  swap(c[x], c[y]);

  int ans = 0;

  for(int val = 0; val < h * w; val++) {
    a[r[val]][c[val]] = 1;
    int match = 0;
//    cout << r[val] << " " << c[val] << endl;
    for(int i = 0; i <= h; i++) for(int j = 0; j <= w; j++) {
      int tmp = calc(i, j);
      if (tmp == 1) match++;
      if (tmp == 3) match = 1e9;
    }
    if (match == 4) ans++;
  }

  for(int val = 0; val < h * w; val++) a[r[val]][c[val]] = 0;

  return ans;
}

#ifdef ngu
int main() {
   freopen ("task.inp", "r", stdin);
   freopen ("task.out", "w", stdout);

   int _h, _w; cin >> _h >> _w;
   vector<int> _r(_h * _w), _c(_h * _w);
   for(int i = 0; i < _h; i++) for(int j = 0; j < _w; j++) {
      int x; cin >> x;
      _r[x] = i;
      _c[x] = j;
   }

   give_initial_chart(_h, _w, _r, _c);

   int q; cin >> q;

   while (q--) {
      int a, b; cin >> a >> b;
      cout << swap_seats(a, b) << endl;
   }
}
#endif // ngu

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 14 ms 4680 KB Output is correct
3 Correct 93 ms 4692 KB Output is correct
4 Correct 159 ms 4692 KB Output is correct
5 Correct 156 ms 4696 KB Output is correct
6 Correct 127 ms 4688 KB Output is correct
7 Correct 109 ms 4692 KB Output is correct
8 Correct 69 ms 4656 KB Output is correct
9 Correct 80 ms 4688 KB Output is correct
10 Correct 119 ms 4952 KB Output is correct
11 Correct 127 ms 4696 KB Output is correct
12 Correct 129 ms 4692 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 14 ms 4680 KB Output is correct
3 Correct 93 ms 4692 KB Output is correct
4 Correct 159 ms 4692 KB Output is correct
5 Correct 156 ms 4696 KB Output is correct
6 Correct 127 ms 4688 KB Output is correct
7 Correct 109 ms 4692 KB Output is correct
8 Correct 69 ms 4656 KB Output is correct
9 Correct 80 ms 4688 KB Output is correct
10 Correct 119 ms 4952 KB Output is correct
11 Correct 127 ms 4696 KB Output is correct
12 Correct 129 ms 4692 KB Output is correct
13 Execution timed out 4019 ms 4952 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4011 ms 40516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 4948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6100 KB Output is correct
2 Correct 44 ms 6144 KB Output is correct
3 Correct 1297 ms 6100 KB Output is correct
4 Execution timed out 4011 ms 5876 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 14 ms 4680 KB Output is correct
3 Correct 93 ms 4692 KB Output is correct
4 Correct 159 ms 4692 KB Output is correct
5 Correct 156 ms 4696 KB Output is correct
6 Correct 127 ms 4688 KB Output is correct
7 Correct 109 ms 4692 KB Output is correct
8 Correct 69 ms 4656 KB Output is correct
9 Correct 80 ms 4688 KB Output is correct
10 Correct 119 ms 4952 KB Output is correct
11 Correct 127 ms 4696 KB Output is correct
12 Correct 129 ms 4692 KB Output is correct
13 Execution timed out 4019 ms 4952 KB Time limit exceeded
14 Halted 0 ms 0 KB -