oj.uz

Submission #888931

# Submission time Handle Problem Language Result Execution time Memory
888931 2023-12-18T12:09:02 Z nguyentunglam Seats (IOI18_seats) C++17
5 / 100
 4000 ms 24640 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;
    }
    assert(match >= 4);
    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 4440 KB Output is correct
2 Correct 14 ms 4636 KB Output is correct
3 Correct 91 ms 4600 KB Output is correct
4 Correct 161 ms 4588 KB Output is correct
5 Correct 150 ms 4688 KB Output is correct
6 Correct 134 ms 4700 KB Output is correct
7 Correct 110 ms 4440 KB Output is correct
8 Correct 69 ms 4444 KB Output is correct
9 Correct 82 ms 4604 KB Output is correct
10 Correct 118 ms 4688 KB Output is correct
11 Correct 127 ms 4632 KB Output is correct
12 Correct 135 ms 4576 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 14 ms 4636 KB Output is correct
3 Correct 91 ms 4600 KB Output is correct
4 Correct 161 ms 4588 KB Output is correct
5 Correct 150 ms 4688 KB Output is correct
6 Correct 134 ms 4700 KB Output is correct
7 Correct 110 ms 4440 KB Output is correct
8 Correct 69 ms 4444 KB Output is correct
9 Correct 82 ms 4604 KB Output is correct
10 Correct 118 ms 4688 KB Output is correct
11 Correct 127 ms 4632 KB Output is correct
12 Correct 135 ms 4576 KB Output is correct
13 Execution timed out 4003 ms 4696 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 4027 ms 24640 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 4026 ms 4696 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 5588 KB Output is correct
2 Correct 44 ms 5592 KB Output is correct
3 Correct 1293 ms 5488 KB Output is correct
4 Execution timed out 4099 ms 5196 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 4440 KB Output is correct
2 Correct 14 ms 4636 KB Output is correct
3 Correct 91 ms 4600 KB Output is correct
4 Correct 161 ms 4588 KB Output is correct
5 Correct 150 ms 4688 KB Output is correct
6 Correct 134 ms 4700 KB Output is correct
7 Correct 110 ms 4440 KB Output is correct
8 Correct 69 ms 4444 KB Output is correct
9 Correct 82 ms 4604 KB Output is correct
10 Correct 118 ms 4688 KB Output is correct
11 Correct 127 ms 4632 KB Output is correct
12 Correct 135 ms 4576 KB Output is correct
13 Execution timed out 4003 ms 4696 KB Time limit exceeded
14 Halted 0 ms 0 KB -