oj.uz

Submission #1051807

# Submission time Handle Problem Language Result Execution time Memory
1051807 2024-08-10T09:55:16 Z MilosMilutinovic Brought Down the Grading Server? (CEOI23_balance) C++14
50 / 100
 383 ms 137676 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) (1e6) + 100;

int ptr[N], from[N], to[N];
vector<int> g[N];
vector<int> euler;
bool was[N];

void dfs(int v) {
  while (ptr[v] < (int) g[v].size()) {
    int e = g[v][ptr[v]];
    if (was[e]) {
      ptr[v] += 1;
      continue;
    }
    int u = (from[e] ^ to[e] ^ v);
    was[e] = true;
    dfs(u);
    ptr[v] += 1;
  }
  euler.push_back(v);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, s, t;
  cin >> n >> s >> t;
  vector<vector<int>> a(n, vector<int>(s));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cin >> a[i][j];
      --a[i][j];
    }
  }
  /* for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
  cout << "t = " << t << endl; */
  vector<vector<int>> res(n, vector<int>(s, -1));
  function<void(int, int, vector<vector<int>>)> Solve = [&](int l, int r, vector<vector<int>> a) {
    if (l == r) {
      for (int i = 0; i < n; i++) {
        res[i][l] = a[i][0];
      }
      return;
    }
    int m = r - l + 1;
    /* vector<vector<int>> pos(t);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        pos[a[i][j]].push_back(i);
      }
    } */
    for (int i = 0; i < n + t; i++) {
      g[i].clear();
      ptr[i] = 0;
    }
    int p = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        from[p] = i;
        to[p] = n + a[i][j];
        g[i].push_back(p);
        g[n + a[i][j]].push_back(p);
        p += 1;
      }
    }
    for (int i = 0; i < p; i++) {
      was[i] = false;
    }
    vector<vector<int>> L(n);
    vector<vector<int>> R(n);
    for (int i = 0; i < n; i++) {
      if (ptr[i] < (int) g[i].size()) {
        euler.clear();
        dfs(i);
        int sz = (int) euler.size();
        for (int i = 0; i < sz; i += 2) {
          if (i + 1 < sz) {
            L[euler[i]].push_back(euler[i + 1] - n);
          }
          if (i > 0) {
            R[euler[i]].push_back(euler[i - 1] - n);
          }
        }
      }
    }
    /* if (l == 0 && r == 1) {
      cout << "euler = ";
      for (int i : euler) {
        cout << i << " ";
      }
      cout << endl;
    }
    if (l == 0 && r == 1) {
      cout << "L" << endl;
      for (int i = 0; i < n; i++) {
        for (int v : L[i]) {
          cout << v << " ";
        }
        cout << endl;
      }
      cout << "R" << endl;
      for (int i = 0; i < n; i++) {
        for (int v : L[i]) {
          cout << v << " ";
        }
        cout << endl;
      } 
    } */
    int mid = (l + r) >> 1;
    Solve(l, mid, L);
    Solve(mid + 1, r, R);
  };
  Solve(0, s - 1, a);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < s; j++) {
      cout << res[i][j] + 1 << " ";
    }
    cout << '\n';
  }
  return 0; 
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 58972 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 58972 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 86736 KB Correct
2 Correct 110 ms 86096 KB Correct
3 Correct 108 ms 78988 KB Correct
4 Correct 63 ms 83196 KB Correct
5 Correct 77 ms 86312 KB Correct
6 Correct 96 ms 87504 KB Correct
7 Correct 86 ms 74324 KB Correct
8 Correct 99 ms 87952 KB Correct
9 Correct 78 ms 87724 KB Correct
10 Correct 67 ms 87780 KB Correct
11 Correct 63 ms 87724 KB Correct

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 86736 KB Correct
2 Correct 110 ms 86096 KB Correct
3 Correct 108 ms 78988 KB Correct
4 Correct 63 ms 83196 KB Correct
5 Correct 77 ms 86312 KB Correct
6 Correct 96 ms 87504 KB Correct
7 Correct 86 ms 74324 KB Correct
8 Correct 99 ms 87952 KB Correct
9 Correct 78 ms 87724 KB Correct
10 Correct 67 ms 87780 KB Correct
11 Correct 63 ms 87724 KB Correct
12 Correct 94 ms 86728 KB Correct
13 Correct 95 ms 86204 KB Correct
14 Correct 92 ms 78988 KB Correct
15 Correct 63 ms 83148 KB Correct
16 Correct 88 ms 86340 KB Correct
17 Correct 89 ms 87504 KB Correct
18 Correct 84 ms 74320 KB Correct
19 Correct 76 ms 87748 KB Correct
20 Correct 81 ms 87680 KB Correct
21 Correct 65 ms 87752 KB Correct
22 Correct 67 ms 87592 KB Correct
23 Runtime error 88 ms 137676 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 58972 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Correct
2 Correct 8 ms 30296 KB Correct
3 Correct 7 ms 30040 KB Correct
4 Correct 6 ms 31144 KB Correct
5 Correct 6 ms 31576 KB Correct
6 Correct 6 ms 31780 KB Correct
7 Correct 7 ms 31196 KB Correct
8 Correct 7 ms 30812 KB Correct
9 Correct 8 ms 30576 KB Correct
10 Correct 7 ms 31068 KB Correct
11 Correct 7 ms 30812 KB Correct
12 Correct 7 ms 31804 KB Correct
13 Correct 7 ms 31784 KB Correct
14 Correct 6 ms 31760 KB Correct

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Correct
2 Correct 8 ms 30296 KB Correct
3 Correct 7 ms 30040 KB Correct
4 Correct 6 ms 31144 KB Correct
5 Correct 6 ms 31576 KB Correct
6 Correct 6 ms 31780 KB Correct
7 Correct 7 ms 31196 KB Correct
8 Correct 7 ms 30812 KB Correct
9 Correct 8 ms 30576 KB Correct
10 Correct 7 ms 31068 KB Correct
11 Correct 7 ms 30812 KB Correct
12 Correct 7 ms 31804 KB Correct
13 Correct 7 ms 31784 KB Correct
14 Correct 6 ms 31760 KB Correct
15 Correct 3 ms 29020 KB Correct
16 Correct 8 ms 30300 KB Correct
17 Correct 7 ms 30044 KB Correct
18 Correct 7 ms 31192 KB Correct
19 Correct 6 ms 31580 KB Correct
20 Correct 6 ms 31672 KB Correct
21 Correct 7 ms 31316 KB Correct
22 Correct 7 ms 30812 KB Correct
23 Correct 7 ms 30508 KB Correct
24 Correct 7 ms 31068 KB Correct
25 Correct 6 ms 30808 KB Correct
26 Correct 7 ms 31808 KB Correct
27 Correct 6 ms 31788 KB Correct
28 Correct 6 ms 31752 KB Correct
29 Runtime error 21 ms 60744 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Correct
2 Correct 8 ms 30296 KB Correct
3 Correct 7 ms 30040 KB Correct
4 Correct 6 ms 31144 KB Correct
5 Correct 6 ms 31576 KB Correct
6 Correct 6 ms 31780 KB Correct
7 Correct 7 ms 31196 KB Correct
8 Correct 7 ms 30812 KB Correct
9 Correct 8 ms 30576 KB Correct
10 Correct 7 ms 31068 KB Correct
11 Correct 7 ms 30812 KB Correct
12 Correct 7 ms 31804 KB Correct
13 Correct 7 ms 31784 KB Correct
14 Correct 6 ms 31760 KB Correct
15 Correct 3 ms 29020 KB Correct
16 Correct 8 ms 30300 KB Correct
17 Correct 7 ms 30044 KB Correct
18 Correct 7 ms 31192 KB Correct
19 Correct 6 ms 31580 KB Correct
20 Correct 6 ms 31672 KB Correct
21 Correct 7 ms 31316 KB Correct
22 Correct 7 ms 30812 KB Correct
23 Correct 7 ms 30508 KB Correct
24 Correct 7 ms 31068 KB Correct
25 Correct 6 ms 30808 KB Correct
26 Correct 7 ms 31808 KB Correct
27 Correct 6 ms 31788 KB Correct
28 Correct 6 ms 31752 KB Correct
29 Runtime error 21 ms 60744 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #4-1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 86736 KB Correct
2 Correct 110 ms 86096 KB Correct
3 Correct 108 ms 78988 KB Correct
4 Correct 63 ms 83196 KB Correct
5 Correct 77 ms 86312 KB Correct
6 Correct 96 ms 87504 KB Correct
7 Correct 86 ms 74324 KB Correct
8 Correct 99 ms 87952 KB Correct
9 Correct 78 ms 87724 KB Correct
10 Correct 67 ms 87780 KB Correct
11 Correct 63 ms 87724 KB Correct
12 Correct 3 ms 29020 KB Correct
13 Correct 8 ms 30296 KB Correct
14 Correct 7 ms 30040 KB Correct
15 Correct 6 ms 31144 KB Correct
16 Correct 6 ms 31576 KB Correct
17 Correct 6 ms 31780 KB Correct
18 Correct 7 ms 31196 KB Correct
19 Correct 7 ms 30812 KB Correct
20 Correct 8 ms 30576 KB Correct
21 Correct 7 ms 31068 KB Correct
22 Correct 7 ms 30812 KB Correct
23 Correct 7 ms 31804 KB Correct
24 Correct 7 ms 31784 KB Correct
25 Correct 6 ms 31760 KB Correct
26 Correct 98 ms 86724 KB Correct
27 Correct 85 ms 85880 KB Correct
28 Correct 88 ms 78984 KB Correct
29 Correct 69 ms 83148 KB Correct
30 Correct 78 ms 86344 KB Correct
31 Correct 91 ms 87556 KB Correct
32 Correct 84 ms 74320 KB Correct
33 Correct 72 ms 87748 KB Correct
34 Correct 75 ms 87720 KB Correct
35 Correct 65 ms 87752 KB Correct
36 Correct 66 ms 87628 KB Correct
37 Correct 4 ms 29020 KB Correct
38 Correct 8 ms 30300 KB Correct
39 Correct 7 ms 30044 KB Correct
40 Correct 7 ms 31140 KB Correct
41 Correct 7 ms 31580 KB Correct
42 Correct 8 ms 31780 KB Correct
43 Correct 8 ms 31196 KB Correct
44 Correct 7 ms 30808 KB Correct
45 Correct 7 ms 30556 KB Correct
46 Correct 7 ms 31068 KB Correct
47 Correct 7 ms 30808 KB Correct
48 Correct 7 ms 31808 KB Correct
49 Correct 7 ms 31788 KB Correct
50 Correct 6 ms 31788 KB Correct
51 Correct 329 ms 116276 KB Correct
52 Correct 308 ms 84952 KB Correct
53 Correct 52 ms 41104 KB Correct
54 Correct 98 ms 56852 KB Correct
55 Correct 284 ms 79928 KB Correct
56 Correct 334 ms 108536 KB Correct
57 Correct 357 ms 116740 KB Correct
58 Correct 298 ms 83900 KB Correct
59 Correct 238 ms 74700 KB Correct
60 Correct 299 ms 103520 KB Correct
61 Correct 383 ms 112412 KB Correct
62 Correct 195 ms 105104 KB Correct
63 Correct 223 ms 105144 KB Correct
64 Correct 185 ms 104924 KB Correct
65 Correct 147 ms 105008 KB Correct
66 Correct 156 ms 106944 KB Correct
67 Correct 156 ms 117600 KB Correct
68 Correct 161 ms 117700 KB Correct
69 Correct 161 ms 113224 KB Correct
70 Correct 196 ms 90352 KB Correct
71 Correct 184 ms 97540 KB Correct

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 86736 KB Correct
2 Correct 110 ms 86096 KB Correct
3 Correct 108 ms 78988 KB Correct
4 Correct 63 ms 83196 KB Correct
5 Correct 77 ms 86312 KB Correct
6 Correct 96 ms 87504 KB Correct
7 Correct 86 ms 74324 KB Correct
8 Correct 99 ms 87952 KB Correct
9 Correct 78 ms 87724 KB Correct
10 Correct 67 ms 87780 KB Correct
11 Correct 63 ms 87724 KB Correct
12 Correct 94 ms 86728 KB Correct
13 Correct 95 ms 86204 KB Correct
14 Correct 92 ms 78988 KB Correct
15 Correct 63 ms 83148 KB Correct
16 Correct 88 ms 86340 KB Correct
17 Correct 89 ms 87504 KB Correct
18 Correct 84 ms 74320 KB Correct
19 Correct 76 ms 87748 KB Correct
20 Correct 81 ms 87680 KB Correct
21 Correct 65 ms 87752 KB Correct
22 Correct 67 ms 87592 KB Correct
23 Runtime error 88 ms 137676 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4-3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 58972 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -