#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 5e5 + 5;
bool vis[N];
int original[N * 2];
vector<pair<int, int>> g[N];
vector<pair<int, int>> occ[N * 2];
void dfs(int v, vector<array<int, 3>>& lx, vector<array<int, 3>>& rx) {
while (!g[v].empty()) {
auto [i, u] = g[v].back();
g[v].pop_back();
if (vis[i]) {
continue;
}
vis[i] = true;
if (v < u) {
rx.push_back({i, v, u});
} else {
lx.push_back({i, u, v});
}
dfs(u, lx, rx);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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];
occ[a[i][j]].push_back({i, j});
}
}
int cnt = t + 1;
for (int i = 1; i <= t; ++i) {
original[i] = i;
while ((int) occ[i].size() > s) {
for (int j = 0; j < s; ++j) {
auto [x, y] = occ[i].back();
occ[i].pop_back();
debug(x, y, cnt);
a[x][y] = cnt;
}
original[cnt] = i;
cnt++;
}
}
//for (int i = 0; i < n; ++i) {
//for (int j = 0; j < s; ++j) {
//cout << a[i][j] << " \n"[j == s - 1];
//}
//}
vector<array<int, 3>> edges;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < s; ++j) {
edges.push_back({i * s + j, i, a[i][j] + n});
}
}
vector<vector<int>> b(n, vector<int> (s));
function<void(int, int, vector<array<int, 3>>)> solve = [&](int l, int r, vector<array<int, 3>> e) {
if (l == r) {
for (auto [i, row, task] : e) {
b[row][l] = original[task - n];
}
return;
}
int mid = (l + r) >> 1;
for (auto [i, u, v] : e) {
vis[i] = false;
g[u].push_back({i, v});
g[v].push_back({i, u});
}
vector<array<int, 3>> lx, rx;
for (auto [i, u, v] : e) {
if (!vis[i]) {
dfs(u, lx, rx);
}
}
solve(l, mid, lx);
solve(mid + 1, r, rx);
};
solve(0, s - 1, edges);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < s; ++j) {
cout << b[i][j] << " \n"[j == s - 1];
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
35676 KB |
Integer 0 violates the range [1, 3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
35676 KB |
Integer 0 violates the range [1, 3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
81088 KB |
Correct |
2 |
Correct |
113 ms |
76100 KB |
Correct |
3 |
Correct |
103 ms |
68608 KB |
Correct |
4 |
Correct |
75 ms |
64952 KB |
Correct |
5 |
Correct |
108 ms |
82136 KB |
Correct |
6 |
Correct |
116 ms |
80328 KB |
Correct |
7 |
Correct |
103 ms |
67064 KB |
Correct |
8 |
Correct |
100 ms |
82884 KB |
Correct |
9 |
Correct |
96 ms |
82628 KB |
Correct |
10 |
Correct |
78 ms |
82880 KB |
Correct |
11 |
Correct |
79 ms |
82624 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
81088 KB |
Correct |
2 |
Correct |
113 ms |
76100 KB |
Correct |
3 |
Correct |
103 ms |
68608 KB |
Correct |
4 |
Correct |
75 ms |
64952 KB |
Correct |
5 |
Correct |
108 ms |
82136 KB |
Correct |
6 |
Correct |
116 ms |
80328 KB |
Correct |
7 |
Correct |
103 ms |
67064 KB |
Correct |
8 |
Correct |
100 ms |
82884 KB |
Correct |
9 |
Correct |
96 ms |
82628 KB |
Correct |
10 |
Correct |
78 ms |
82880 KB |
Correct |
11 |
Correct |
79 ms |
82624 KB |
Correct |
12 |
Correct |
113 ms |
81088 KB |
Correct |
13 |
Correct |
105 ms |
76012 KB |
Correct |
14 |
Correct |
103 ms |
68800 KB |
Correct |
15 |
Correct |
74 ms |
65076 KB |
Correct |
16 |
Correct |
101 ms |
82112 KB |
Correct |
17 |
Correct |
116 ms |
80328 KB |
Correct |
18 |
Correct |
110 ms |
67212 KB |
Correct |
19 |
Correct |
100 ms |
82876 KB |
Correct |
20 |
Correct |
94 ms |
82732 KB |
Correct |
21 |
Correct |
79 ms |
82832 KB |
Correct |
22 |
Correct |
82 ms |
82624 KB |
Correct |
23 |
Incorrect |
109 ms |
68912 KB |
Integer 0 violates the range [1, 100000] |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
35676 KB |
Integer 0 violates the range [1, 3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35672 KB |
Correct |
2 |
Correct |
21 ms |
37560 KB |
Correct |
3 |
Correct |
23 ms |
37172 KB |
Correct |
4 |
Correct |
20 ms |
37672 KB |
Correct |
5 |
Correct |
17 ms |
36984 KB |
Correct |
6 |
Correct |
19 ms |
37740 KB |
Correct |
7 |
Correct |
19 ms |
37452 KB |
Correct |
8 |
Correct |
18 ms |
37660 KB |
Correct |
9 |
Correct |
18 ms |
37124 KB |
Correct |
10 |
Correct |
19 ms |
37432 KB |
Correct |
11 |
Correct |
18 ms |
37400 KB |
Correct |
12 |
Correct |
17 ms |
37920 KB |
Correct |
13 |
Correct |
17 ms |
37912 KB |
Correct |
14 |
Correct |
17 ms |
37916 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35672 KB |
Correct |
2 |
Correct |
21 ms |
37560 KB |
Correct |
3 |
Correct |
23 ms |
37172 KB |
Correct |
4 |
Correct |
20 ms |
37672 KB |
Correct |
5 |
Correct |
17 ms |
36984 KB |
Correct |
6 |
Correct |
19 ms |
37740 KB |
Correct |
7 |
Correct |
19 ms |
37452 KB |
Correct |
8 |
Correct |
18 ms |
37660 KB |
Correct |
9 |
Correct |
18 ms |
37124 KB |
Correct |
10 |
Correct |
19 ms |
37432 KB |
Correct |
11 |
Correct |
18 ms |
37400 KB |
Correct |
12 |
Correct |
17 ms |
37920 KB |
Correct |
13 |
Correct |
17 ms |
37912 KB |
Correct |
14 |
Correct |
17 ms |
37916 KB |
Correct |
15 |
Correct |
17 ms |
35672 KB |
Correct |
16 |
Correct |
19 ms |
37560 KB |
Correct |
17 |
Correct |
21 ms |
37168 KB |
Correct |
18 |
Correct |
19 ms |
37644 KB |
Correct |
19 |
Correct |
19 ms |
36980 KB |
Correct |
20 |
Correct |
19 ms |
37684 KB |
Correct |
21 |
Correct |
18 ms |
37448 KB |
Correct |
22 |
Correct |
22 ms |
37564 KB |
Correct |
23 |
Correct |
20 ms |
37156 KB |
Correct |
24 |
Correct |
21 ms |
37468 KB |
Correct |
25 |
Correct |
20 ms |
37404 KB |
Correct |
26 |
Correct |
24 ms |
37920 KB |
Correct |
27 |
Correct |
21 ms |
37916 KB |
Correct |
28 |
Correct |
20 ms |
37916 KB |
Correct |
29 |
Incorrect |
22 ms |
37540 KB |
Integer 0 violates the range [1, 50] |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
35672 KB |
Correct |
2 |
Correct |
21 ms |
37560 KB |
Correct |
3 |
Correct |
23 ms |
37172 KB |
Correct |
4 |
Correct |
20 ms |
37672 KB |
Correct |
5 |
Correct |
17 ms |
36984 KB |
Correct |
6 |
Correct |
19 ms |
37740 KB |
Correct |
7 |
Correct |
19 ms |
37452 KB |
Correct |
8 |
Correct |
18 ms |
37660 KB |
Correct |
9 |
Correct |
18 ms |
37124 KB |
Correct |
10 |
Correct |
19 ms |
37432 KB |
Correct |
11 |
Correct |
18 ms |
37400 KB |
Correct |
12 |
Correct |
17 ms |
37920 KB |
Correct |
13 |
Correct |
17 ms |
37912 KB |
Correct |
14 |
Correct |
17 ms |
37916 KB |
Correct |
15 |
Correct |
17 ms |
35672 KB |
Correct |
16 |
Correct |
19 ms |
37560 KB |
Correct |
17 |
Correct |
21 ms |
37168 KB |
Correct |
18 |
Correct |
19 ms |
37644 KB |
Correct |
19 |
Correct |
19 ms |
36980 KB |
Correct |
20 |
Correct |
19 ms |
37684 KB |
Correct |
21 |
Correct |
18 ms |
37448 KB |
Correct |
22 |
Correct |
22 ms |
37564 KB |
Correct |
23 |
Correct |
20 ms |
37156 KB |
Correct |
24 |
Correct |
21 ms |
37468 KB |
Correct |
25 |
Correct |
20 ms |
37404 KB |
Correct |
26 |
Correct |
24 ms |
37920 KB |
Correct |
27 |
Correct |
21 ms |
37916 KB |
Correct |
28 |
Correct |
20 ms |
37916 KB |
Correct |
29 |
Incorrect |
22 ms |
37540 KB |
Integer 0 violates the range [1, 50] |
30 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
81088 KB |
Correct |
2 |
Correct |
113 ms |
76100 KB |
Correct |
3 |
Correct |
103 ms |
68608 KB |
Correct |
4 |
Correct |
75 ms |
64952 KB |
Correct |
5 |
Correct |
108 ms |
82136 KB |
Correct |
6 |
Correct |
116 ms |
80328 KB |
Correct |
7 |
Correct |
103 ms |
67064 KB |
Correct |
8 |
Correct |
100 ms |
82884 KB |
Correct |
9 |
Correct |
96 ms |
82628 KB |
Correct |
10 |
Correct |
78 ms |
82880 KB |
Correct |
11 |
Correct |
79 ms |
82624 KB |
Correct |
12 |
Correct |
14 ms |
35672 KB |
Correct |
13 |
Correct |
21 ms |
37560 KB |
Correct |
14 |
Correct |
23 ms |
37172 KB |
Correct |
15 |
Correct |
20 ms |
37672 KB |
Correct |
16 |
Correct |
17 ms |
36984 KB |
Correct |
17 |
Correct |
19 ms |
37740 KB |
Correct |
18 |
Correct |
19 ms |
37452 KB |
Correct |
19 |
Correct |
18 ms |
37660 KB |
Correct |
20 |
Correct |
18 ms |
37124 KB |
Correct |
21 |
Correct |
19 ms |
37432 KB |
Correct |
22 |
Correct |
18 ms |
37400 KB |
Correct |
23 |
Correct |
17 ms |
37920 KB |
Correct |
24 |
Correct |
17 ms |
37912 KB |
Correct |
25 |
Correct |
17 ms |
37916 KB |
Correct |
26 |
Correct |
109 ms |
81068 KB |
Correct |
27 |
Correct |
115 ms |
76100 KB |
Correct |
28 |
Correct |
97 ms |
68812 KB |
Correct |
29 |
Correct |
77 ms |
65072 KB |
Correct |
30 |
Correct |
105 ms |
82156 KB |
Correct |
31 |
Correct |
119 ms |
80340 KB |
Correct |
32 |
Correct |
111 ms |
67268 KB |
Correct |
33 |
Correct |
102 ms |
82836 KB |
Correct |
34 |
Correct |
104 ms |
82628 KB |
Correct |
35 |
Correct |
78 ms |
82940 KB |
Correct |
36 |
Correct |
79 ms |
82628 KB |
Correct |
37 |
Correct |
17 ms |
35672 KB |
Correct |
38 |
Correct |
20 ms |
37440 KB |
Correct |
39 |
Correct |
26 ms |
37328 KB |
Correct |
40 |
Correct |
19 ms |
37672 KB |
Correct |
41 |
Correct |
21 ms |
37180 KB |
Correct |
42 |
Correct |
18 ms |
37684 KB |
Correct |
43 |
Correct |
21 ms |
37452 KB |
Correct |
44 |
Correct |
19 ms |
37660 KB |
Correct |
45 |
Correct |
21 ms |
37148 KB |
Correct |
46 |
Correct |
18 ms |
37464 KB |
Correct |
47 |
Correct |
26 ms |
37404 KB |
Correct |
48 |
Correct |
23 ms |
37920 KB |
Correct |
49 |
Correct |
19 ms |
37920 KB |
Correct |
50 |
Correct |
21 ms |
37920 KB |
Correct |
51 |
Correct |
355 ms |
129956 KB |
Correct |
52 |
Correct |
342 ms |
122936 KB |
Correct |
53 |
Correct |
77 ms |
52652 KB |
Correct |
54 |
Correct |
116 ms |
70468 KB |
Correct |
55 |
Correct |
297 ms |
114904 KB |
Correct |
56 |
Correct |
326 ms |
126140 KB |
Correct |
57 |
Correct |
340 ms |
130648 KB |
Correct |
58 |
Correct |
331 ms |
121824 KB |
Correct |
59 |
Correct |
284 ms |
107096 KB |
Correct |
60 |
Correct |
245 ms |
105652 KB |
Correct |
61 |
Correct |
316 ms |
125108 KB |
Correct |
62 |
Correct |
157 ms |
117436 KB |
Correct |
63 |
Correct |
153 ms |
103348 KB |
Correct |
64 |
Correct |
149 ms |
103356 KB |
Correct |
65 |
Correct |
138 ms |
101304 KB |
Correct |
66 |
Correct |
145 ms |
101568 KB |
Correct |
67 |
Correct |
145 ms |
101320 KB |
Correct |
68 |
Correct |
145 ms |
100864 KB |
Correct |
69 |
Correct |
137 ms |
101608 KB |
Correct |
70 |
Correct |
194 ms |
125936 KB |
Correct |
71 |
Correct |
208 ms |
127868 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
81088 KB |
Correct |
2 |
Correct |
113 ms |
76100 KB |
Correct |
3 |
Correct |
103 ms |
68608 KB |
Correct |
4 |
Correct |
75 ms |
64952 KB |
Correct |
5 |
Correct |
108 ms |
82136 KB |
Correct |
6 |
Correct |
116 ms |
80328 KB |
Correct |
7 |
Correct |
103 ms |
67064 KB |
Correct |
8 |
Correct |
100 ms |
82884 KB |
Correct |
9 |
Correct |
96 ms |
82628 KB |
Correct |
10 |
Correct |
78 ms |
82880 KB |
Correct |
11 |
Correct |
79 ms |
82624 KB |
Correct |
12 |
Correct |
113 ms |
81088 KB |
Correct |
13 |
Correct |
105 ms |
76012 KB |
Correct |
14 |
Correct |
103 ms |
68800 KB |
Correct |
15 |
Correct |
74 ms |
65076 KB |
Correct |
16 |
Correct |
101 ms |
82112 KB |
Correct |
17 |
Correct |
116 ms |
80328 KB |
Correct |
18 |
Correct |
110 ms |
67212 KB |
Correct |
19 |
Correct |
100 ms |
82876 KB |
Correct |
20 |
Correct |
94 ms |
82732 KB |
Correct |
21 |
Correct |
79 ms |
82832 KB |
Correct |
22 |
Correct |
82 ms |
82624 KB |
Correct |
23 |
Incorrect |
109 ms |
68912 KB |
Integer 0 violates the range [1, 100000] |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
35676 KB |
Integer 0 violates the range [1, 3] |
2 |
Halted |
0 ms |
0 KB |
- |