QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#479727 | #999. 边双连通分量 | NOI_AK_ME# | AC ✓ | 26ms | 21584kb | C++23 | 18.1kb | 2024-07-15 20:34:13 | 2024-07-15 20:34:13 |
Judging History
answer
#include <algorithm>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <numeric>
#include <vector>
#include <string>
#ifndef __OY_LINUXIO__
#define __OY_LINUXIO__
#ifdef __unix__
#include <sys/mman.h>
#include <sys/stat.h>
#endif
#if __cpp_constexpr >= 201907L
#define CONSTEXPR20 constexpr
#define INLINE20 constexpr
#else
#define CONSTEXPR20
#define INLINE20 inline
#endif
#define cin OY::LinuxIO::InputHelper<>::get_instance()
#define cout OY::LinuxIO::OutputHelper::get_instance()
#define endl '\n'
#ifndef INPUT_FILE
#define INPUT_FILE "in.txt"
#endif
#ifndef OUTPUT_FILE
#define OUTPUT_FILE "out.txt"
#endif
namespace OY {
namespace LinuxIO {
static constexpr size_t INPUT_BUFFER_SIZE = 1 << 26, OUTPUT_BUFFER_SIZE = 1 << 20;
#ifdef OY_LOCAL
static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
template <typename U, size_t E>
struct TenPow {
static constexpr U value = TenPow<U, E - 1>::value * 10;
};
template <typename U>
struct TenPow<U, 0> {
static constexpr U value = 1;
};
struct InputPre {
uint32_t m_data[0x10000];
CONSTEXPR20 InputPre() {
std::fill(m_data, m_data + 0x10000, -1);
for (size_t i = 0, val = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++) m_data[0x3030 + i + (j << 8)] = val++;
}
};
struct OutputPre {
uint32_t m_data[10000];
CONSTEXPR20 OutputPre() {
uint32_t *c = m_data;
for (size_t i = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++)
for (size_t k = 0; k != 10; k++)
for (size_t l = 0; l != 10; l++) *c++ = i + (j << 8) + (k << 16) + (l << 24) + 0x30303030;
}
};
template <size_t MMAP_SIZE = 1 << 30>
struct InputHelper {
static INLINE20 InputPre pre{};
struct stat m_stat;
char *m_p, *m_c, *m_end;
InputHelper(FILE *file = stdin) {
#ifdef __unix__
auto fd = fileno(file);
fstat(fd, &m_stat);
m_c = m_p = (char *)mmap(nullptr, m_stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
m_end = m_p + m_stat.st_size;
#else
uint32_t size = fread(m_c = m_p = new char[INPUT_BUFFER_SIZE], 1, INPUT_BUFFER_SIZE, file);
m_end = m_p + size;
#endif
}
static InputHelper<MMAP_SIZE> &get_instance() {
static InputHelper<MMAP_SIZE> s_obj(*input_file ? fopen(input_file, "rt") : stdin);
return s_obj;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x) {
x = 0;
while (!isdigit(*m_c)) m_c++;
x = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) x = x * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c)) x = x * 10 + (*m_c++ ^ '0');
return *this;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x) {
typename std::make_unsigned<Tp>::type t{};
bool sign{};
while (!isdigit(*m_c)) sign = (*m_c++ == '-');
t = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) t = t * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c)) t = t * 10 + (*m_c++ ^ '0');
x = sign ? -t : t;
return *this;
}
InputHelper &operator>>(char &x) {
while (*m_c <= ' ') m_c++;
x = *m_c++;
return *this;
}
InputHelper &operator>>(std::string &x) {
while (*m_c <= ' ') m_c++;
char *c = m_c;
while (*c > ' ') c++;
x.assign(m_c, c - m_c), m_c = c;
return *this;
}
InputHelper &operator>>(std::string_view &x) {
while (*m_c <= ' ') m_c++;
char *c = m_c;
while (*c > ' ') c++;
x = std::string_view(m_c, c - m_c), m_c = c;
return *this;
}
};
struct OutputHelper {
static INLINE20 OutputPre pre{};
FILE *m_file;
char m_p[OUTPUT_BUFFER_SIZE], *m_c, *m_end;
OutputHelper(FILE *file = stdout) {
m_file = file;
m_c = m_p, m_end = m_p + OUTPUT_BUFFER_SIZE;
}
~OutputHelper() { flush(); }
static OutputHelper &get_instance() {
static OutputHelper s_obj(*output_file ? fopen(output_file, "wt") : stdout);
return s_obj;
}
void flush() { fwrite(m_p, 1, m_c - m_p, m_file), m_c = m_p; }
OutputHelper &operator<<(char x) {
if (m_end - m_c < 20) flush();
*m_c++ = x;
return *this;
}
OutputHelper &operator<<(std::string_view s) {
if (m_end - m_c < s.size()) flush();
memcpy(m_c, s.data(), s.size()), m_c += s.size();
return *this;
}
OutputHelper &operator<<(uint64_t x) {
if (m_end - m_c < 20) flush();
#define CASEW(w) \
case TenPow<uint64_t, w - 1>::value... TenPow<uint64_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint64_t, w - 4>::value;
switch (x) {
CASEW(19);
CASEW(15);
CASEW(11);
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
CASEW(18);
CASEW(14);
CASEW(10);
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(17);
CASEW(13);
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, 16>::value];
m_c += 4;
x %= TenPow<uint64_t, 16>::value;
CASEW(16);
CASEW(12);
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(uint32_t x) {
if (m_end - m_c < 20) flush();
#define CASEW(w) \
case TenPow<uint32_t, w - 1>::value... TenPow<uint32_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint32_t, w - 4>::value;
switch (x) {
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, 6>::value];
m_c += 4;
x %= TenPow<uint32_t, 6>::value;
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(int64_t x) {
if (x >= 0)
return (*this) << uint64_t(x);
else
return (*this) << '-' << uint64_t(-x);
}
OutputHelper &operator<<(int32_t x) {
if (x >= 0)
return (*this) << uint32_t(x);
else
return (*this) << '-' << uint32_t(-x);
}
};
}
}
#endif
#ifndef __OY_TARJAN_BRIDGE__
#define __OY_TARJAN_BRIDGE__
namespace OY {
namespace EBCC {
using size_type = uint32_t;
template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
struct Solver {
struct info {
size_type m_dfn, m_low;
};
static info s_info_buffer[MAX_VERTEX];
static size_type s_ebcc_buffer[MAX_VERTEX * 3], s_use_count, s_edge_use_count;
static bool s_buffer[MAX_EDGE];
info *m_info;
size_type m_vertex_cnt, m_edge_cnt, m_dfn_cnt, m_bridge_cnt, m_ebcc_cnt, m_stack_len, *m_starts, *m_stack, *m_ebccs;
bool *m_is_bridge;
template <typename Traverser>
void _dfs(size_type i, size_type from, Traverser &&traverser) {
size_type pos = m_stack_len;
if constexpr (GetEBCC) m_stack[m_stack_len++] = i;
m_info[i].m_dfn = m_info[i].m_low = m_dfn_cnt++;
traverser(i, [&](size_type index, size_type to) {
if (!~m_info[to].m_dfn) {
_dfs(to, index, traverser);
m_info[i].m_low = std::min(m_info[i].m_low, m_info[to].m_low);
} else if (index != from)
m_info[i].m_low = std::min(m_info[i].m_low, m_info[to].m_dfn);
});
if (m_info[i].m_low != m_info[i].m_dfn) return;
if constexpr (GetEBCC) std::copy(m_stack + pos, m_stack + m_stack_len, m_ebccs + (m_starts[m_ebcc_cnt++] = m_dfn_cnt - m_stack_len)), m_stack_len = pos;
if constexpr (GetBridge)
if (~from) m_is_bridge[from] = true, m_bridge_cnt++;
}
Solver(size_type vertex_cnt, size_type edge_cnt) { m_vertex_cnt = vertex_cnt, m_edge_cnt = edge_cnt, m_dfn_cnt = m_bridge_cnt = m_ebcc_cnt = m_stack_len = 0, m_info = s_info_buffer + s_use_count, m_starts = s_ebcc_buffer + s_use_count * 3, m_stack = s_ebcc_buffer + s_use_count * 3 + m_vertex_cnt, m_ebccs = s_ebcc_buffer + s_use_count * 3 + m_vertex_cnt * 2, m_is_bridge = s_buffer + s_edge_use_count, s_use_count += m_vertex_cnt, s_edge_use_count += m_edge_cnt; }
template <typename Traverser>
void run(Traverser &&traverser) {
for (size_type i = 0; i != m_vertex_cnt; i++) m_info[i].m_dfn = -1;
for (size_type i = 0; i != m_vertex_cnt; i++)
if (!~m_info[i].m_dfn) _dfs(i, -1, traverser);
if constexpr (GetEBCC) m_starts[m_ebcc_cnt] = m_vertex_cnt;
}
template <typename Callback>
void do_for_each_ebcc(Callback &&call) {
for (size_type i = 0, cur = m_starts[0], end = m_starts[1]; i != m_ebcc_cnt; cur = end, end = m_starts[++i + 1]) call(m_ebccs + cur, m_ebccs + end);
}
template <typename Callback>
void do_for_each_bridge(Callback &&call) {
for (size_type index = 0; index != m_edge_cnt; index++)
if (m_is_bridge[index]) call(index);
}
};
template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
typename Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::info Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_info_buffer[MAX_VERTEX];
template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
bool Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_buffer[MAX_EDGE];
template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
size_type Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_ebcc_buffer[MAX_VERTEX * 3];
template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
size_type Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_use_count;
template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
size_type Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_edge_use_count;
template <size_type MAX_VERTEX, size_type MAX_EDGE>
struct Graph {
struct edge {
size_type m_from, m_to;
};
struct adj {
size_type m_index, m_to;
};
static size_type s_buffer[MAX_VERTEX << 1], s_use_count, s_edge_use_count;
static edge s_edge_buffer[MAX_EDGE];
static adj s_adj_buffer[MAX_EDGE << 1];
size_type m_vertex_cnt, m_edge_cnt, *m_starts;
edge *m_edges;
adj *m_adj;
mutable bool m_prepared;
void _prepare() const {
if (m_prepared) return;
m_prepared = true;
for (size_type i = 0; i != m_edge_cnt; i++) m_starts[m_edges[i].m_from + 1]++, m_starts[m_edges[i].m_to + 1]++;
for (size_type i = 1; i != m_vertex_cnt + 1; i++) m_starts[i] += m_starts[i - 1];
std::vector<size_type> cursor(m_starts, m_starts + m_vertex_cnt);
for (size_type i = 0; i != m_edge_cnt; i++) {
size_type from = m_edges[i].m_from, to = m_edges[i].m_to;
m_adj[cursor[from]++] = {i, to}, m_adj[cursor[to]++] = {i, from};
}
}
template <typename Callback>
void operator()(size_type from, Callback &&call) const {
for (size_type cur = m_starts[from], end = m_starts[from + 1]; cur != end; cur++) call(m_adj[cur].m_index, m_adj[cur].m_to);
}
Graph(size_type vertex_cnt = 0, size_type edge_cnt = 0) { resize(vertex_cnt, edge_cnt); }
void resize(size_type vertex_cnt, size_type edge_cnt) {
if (!(m_vertex_cnt = vertex_cnt)) return;
m_prepared = false, m_starts = s_buffer + (s_use_count << 1), m_edges = s_edge_buffer + s_edge_use_count, m_adj = s_adj_buffer + (s_edge_use_count << 1), m_edge_cnt = 0, s_use_count += m_vertex_cnt, s_edge_use_count += edge_cnt;
}
void add_edge(size_type a, size_type b) { m_edges[m_edge_cnt++] = {a, b}; }
template <bool GetBridge, bool GetEBCC>
Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE> calc() const {
_prepare();
Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE> sol(m_vertex_cnt, m_edge_cnt);
sol.run(*this);
return sol;
}
std::vector<std::vector<size_type>> get_ebccs() const {
_prepare();
Solver<false, true, MAX_VERTEX, MAX_EDGE> sol(m_vertex_cnt, m_edge_cnt);
sol.run(*this);
std::vector<std::vector<size_type>> res;
res.reserve(sol.m_ebcc_cnt);
sol.do_for_each_ebcc([&](size_type *first, size_type *last) { res.emplace_back(first, last); });
return res;
}
std::vector<size_type> get_bridges() const {
_prepare();
Solver<true, false, MAX_VERTEX, MAX_EDGE> sol(m_vertex_cnt, m_edge_cnt);
sol.run(*this);
std::vector<size_type> res;
res.reserve(sol.m_bridge_cnt);
sol.do_for_each_bridge([&](size_type index) { res.push_back(index); });
return res;
}
};
template <size_type MAX_VERTEX, size_type MAX_EDGE>
size_type Graph<MAX_VERTEX, MAX_EDGE>::s_buffer[MAX_VERTEX << 1];
template <size_type MAX_VERTEX, size_type MAX_EDGE>
typename Graph<MAX_VERTEX, MAX_EDGE>::edge Graph<MAX_VERTEX, MAX_EDGE>::s_edge_buffer[MAX_EDGE];
template <size_type MAX_VERTEX, size_type MAX_EDGE>
typename Graph<MAX_VERTEX, MAX_EDGE>::adj Graph<MAX_VERTEX, MAX_EDGE>::s_adj_buffer[MAX_EDGE << 1];
template <size_type MAX_VERTEX, size_type MAX_EDGE>
size_type Graph<MAX_VERTEX, MAX_EDGE>::s_use_count;
template <size_type MAX_VERTEX, size_type MAX_EDGE>
size_type Graph<MAX_VERTEX, MAX_EDGE>::s_edge_use_count;
}
}
#endif
static constexpr uint32_t N = 200000, M = 200000;
int main() {
uint32_t n, m;
cin >> n >> m;
OY::EBCC::Graph<N, M> G(n, m);
for (uint32_t i = 0; i != m; i++) {
uint32_t a, b;
cin >> a >> b;
G.add_edge(a, b);
}
auto sol = G.calc<false, true>();
cout << sol.m_ebcc_cnt << endl;
sol.do_for_each_ebcc([&](auto first, auto last) {
cout << last - first;
for (auto it = first; it != last; ++it) cout << ' ' << *it;
cout << endl;
});
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9920kb
input:
4 5 0 2 0 1 3 0 2 1 2 3
output:
1 4 0 2 1 3
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 9824kb
input:
13 21 4 5 8 7 12 3 3 10 1 5 10 2 0 0 11 4 2 12 9 1 9 0 7 8 7 6 9 1 8 2 12 10 11 0 8 6 3 2 5 9 4 11
output:
3 6 0 9 1 5 4 11 3 8 7 6 4 2 10 3 12
result:
ok OK
Test #3:
score: 0
Accepted
time: 1ms
memory: 9756kb
input:
2 2 0 1 1 0
output:
1 2 0 1
result:
ok OK
Test #4:
score: 0
Accepted
time: 26ms
memory: 21584kb
input:
200000 200000 127668 148778 77100 11865 85144 199231 39485 84917 102044 187263 130204 174776 26220 198288 162188 12078 92196 146334 120537 38083 150353 160479 18707 6545 101149 25450 62271 9177 38892 6454 11709 191939 89247 145109 140599 121858 197410 148980 55975 169098 128576 59852 68224 182347 89...
output:
105340 1 130053 1 109379 1 16951 1 96939 1 134977 1 83121 1 114344 1 49994 1 179006 1 197312 1 73479 1 106040 1 50807 1 165221 1 166649 1 68272 1 38289 1 142682 1 99836 1 12028 1 102803 1 27099 1 114474 1 82079 1 104348 1 189374 1 92254 1 150379 1 159181 1 179811 1 140286 1 82857 1 100000 1 127708 1...
result:
ok OK
Test #5:
score: 0
Accepted
time: 26ms
memory: 21424kb
input:
200000 200000 150762 148756 172967 108322 69862 125085 84513 111056 141009 156725 36311 103205 31879 79919 62895 63377 21697 115522 161610 160423 113104 10277 106927 168428 136657 198931 52292 164110 149020 7038 115111 112823 35584 124385 45429 191603 96444 30523 195578 149089 160105 58103 139792 27...
output:
104955 1 125898 1 70394 1 53869 1 104669 1 129081 1 100681 1 41198 1 70879 1 112530 1 14934 1 108660 1 66365 1 24383 1 34481 1 138878 1 86552 1 89618 1 38043 1 54490 1 66419 1 120222 1 140638 1 17682 1 72554 1 89319 1 193209 1 93 1 171935 1 46988 1 199955 1 24166 1 9540 1 16383 1 642 1 137446 1 1176...
result:
ok OK
Test #6:
score: 0
Accepted
time: 15ms
memory: 21408kb
input:
200000 200000 53335 120202 193029 92221 8244 61648 50176 7825 97274 91479 85438 76999 26861 80116 162826 198446 160509 95916 143190 116619 121254 192931 121545 132273 149400 91882 97032 5048 179008 82221 187475 70697 159074 65868 158744 94466 120006 170635 36429 162768 61114 17876 131798 188508 1080...
output:
105649 1 29517 1 154139 1 130698 1 99640 1 140367 1 102247 1 198683 1 47273 1 187909 1 46326 1 22215 1 14473 1 189501 1 117986 1 18389 1 7084 1 132284 1 18675 1 32418 1 43432 1 156817 1 163858 1 151921 1 45282 1 153512 1 50415 1 7040 1 82344 1 100960 1 23893 1 81617 1 43176 1 143595 1 149608 1 60574...
result:
ok OK
Test #7:
score: 0
Accepted
time: 17ms
memory: 18784kb
input:
127669 148779 124640 77100 11865 117450 85144 68159 104241 39485 76372 84917 102044 56191 43704 26220 67216 31116 75749 123504 12078 92196 70006 15262 100591 74552 120537 38083 19281 29407 18707 6545 101149 25450 62271 9177 38892 6454 11709 119710 60867 89247 14037 9527 121858 66338 112298 81804 795...
output:
51131 1 94756 1 44517 1 47153 1 51915 1 12486 1 12214 1 98478 1 14748 1 53706 1 38686 1 22698 1 123435 1 15671 1 108457 1 98869 1 23082 1 76922 1 81699 1 29456 1 10660 1 83810 1 81407 1 30201 1 100714 1 103512 1 97281 1 24849 1 34179 1 80101 1 64953 1 113025 1 34833 1 30346 1 95686 1 84205 1 111115 ...
result:
ok OK
Test #8:
score: 0
Accepted
time: 16ms
memory: 18988kb
input:
150763 148757 108322 69862 125085 84513 111056 141009 36311 103205 31879 79919 62895 63377 21697 115522 113104 10277 106927 136657 52292 149020 7038 115111 112823 35584 124385 45429 96444 30523 149089 58103 139792 27250 15883 109949 69372 132387 141930 113408 65522 128254 138198 141969 42522 92075 1...
output:
81019 1 6807 1 71992 1 6544 1 19114 1 55003 1 109404 1 63787 1 123739 1 41567 1 123431 1 59083 1 114167 1 61359 1 29409 1 59280 1 14684 1 112390 1 145242 1 66891 1 137369 1 84292 1 90202 1 100462 1 3126 1 127606 1 29538 1 76163 1 18555 1 140975 1 41127 1 127342 1 27999 1 93788 1 46914 1 11681 1 1340...
result:
ok OK
Test #9:
score: 0
Accepted
time: 5ms
memory: 15652kb
input:
53336 120203 26685 8244 50176 7825 31738 24370 25943 19902 11463 26861 29977 26309 14580 31754 1838 29437 30380 12118 51083 31633 1201 18328 26346 5295 48935 19027 31496 19906 41783 5048 47936 16685 5161 34107 15907 28002 332 27672 28930 39563 36429 31696 17876 726 42526 21682 35319 8727 17974 25252...
output:
3392 1 14547 1 33221 1 25373 1 49362 1 14444 1 28138 1 46202 1 10768 1 17577 1 12568 1 28744 1 37853 1 593 1 10608 1 5154 1 52185 1 33099 1 50252 1 8805 1 40238 1 20189 1 10803 1 26670 1 490 1 28244 1 13456 1 19261 1 31450 1 7461 1 20204 1 20001 1 18973 1 26131 1 6366 1 28795 1 43905 1 30583 1 26214...
result:
ok OK
Test #10:
score: 0
Accepted
time: 5ms
memory: 11572kb
input:
17707 71661 1354 3272 13699 17294 16733 9246 14993 5758 7252 2983 3813 6121 10450 14069 8088 11201 857 4420 12788 2032 11938 1465 10322 15171 14688 1857 2309 2742 2013 13200 14142 16319 10541 1922 10368 1516 7994 9092 3327 5166 13484 2876 15472 13522 15622 13479 3361 15314 15464 14974 17637 7535 435...
output:
75 1 17338 1 14797 1 3260 1 16007 1 9278 1 15699 1 12609 1 2548 1 12296 1 9486 1 7016 1 13118 1 8246 1 13212 1 5626 1 12473 1 14567 1 10678 1 8347 1 1786 1 8803 1 13636 1 5868 1 15222 1 5980 1 10131 1 12703 1 5504 1 13541 1 14057 1 9878 1 13333 1 17102 1 6026 1190 7795 7124 13409 7421 16327 14686 12...
result:
ok OK
Test #11:
score: 0
Accepted
time: 2ms
memory: 8356kb
input:
4294 17517 1175 3250 314 389 4272 3633 2938 1831 1307 2818 3321 347 1205 1428 2354 1478 1003 3898 1587 3443 1122 1512 2512 3995 348 3280 2064 1022 1834 2958 4281 1863 689 3613 2115 3708 1645 1488 1601 4181 916 4276 128 2626 4147 2868 87 1411 1802 1451 1254 2010 2936 3120 1065 277 1121 3284 3655 2849...
output:
29 1 3537 1 3593 1 3962 1 1431 1 3777 1 1575 198 2662 2474 3414 913 517 1232 2377 2561 1729 1396 3844 2169 2482 1754 1004 1474 2363 674 3884 839 188 2841 290 1191 691 2067 1558 1599 3478 3461 3430 478 3429 1492 3952 2278 1650 864 3422 3797 2929 2903 3016 919 1526 3361 4150 45 1498 176 3137 552 2071 ...
result:
ok OK
Test #12:
score: 0
Accepted
time: 0ms
memory: 13908kb
input:
26686 105813 14774 5315 22701 21346 1398 13888 18566 18745 22298 6181 21347 10653 16500 23768 2329 5818 17512 16769 25519 338 12580 3064 19467 21665 3978 13202 23556 25178 195 9695 1472 13111 22925 24074 3026 13281 17666 14469 22007 18680 4159 13152 20431 23814 6671 10788 24433 13211 9794 12608 3264...
output:
137 1 23394 1 12475 1 2118 1 13345 1 2141 1 22100 1 2499 1 24377 1 1538 1 8709 1 6744 1 16355 1 10300 1 1219 1 10070 1 18834 1 5841 1 13843 1 23868 1 15273 1 26505 1 6022 1 20785 1 8727 1 18510 1 651 1 15559 1 8682 1 17160 1 8793 1 22179 1 26437 1 5458 1 12486 1 371 1 10917 1 24928 1 22401 1 25296 1...
result:
ok OK
Test #13:
score: 0
Accepted
time: 8ms
memory: 12412kb
input:
36033 148595 33366 22486 14414 23855 2694 30361 16352 31902 27993 2048 4707 31743 30610 12884 23278 27069 10529 20914 2030 30015 24554 15673 10184 29423 17825 20383 34077 1181 25518 26129 6355 8810 2857 21736 25108 34280 14992 24299 32649 20227 34529 10407 23194 29913 10451 319 34666 8904 30811 3003...
output:
150 1 7683 1 26444 1 2952 1 909 1 29816 1 28914 1 24825 1 7652 1 32601 1 15933 1 35383 1 10070 1 206 1 26526 1 2237 1 28026 1 2228 1 10445 1 20693 1 31025 1 16543 1 14407 7961 0 28838 10061 799 14110 29442 20494 31404 26764 28991 24773 12616 16339 23468 22326 17303 32977 23324 10223 29873 3162 9601 ...
result:
ok OK
Test #14:
score: 0
Accepted
time: 0ms
memory: 11240kb
input:
14868 57739 5724 2103 9214 3074 2269 531 3811 13162 5199 12632 6337 12078 12592 4977 3553 6975 5063 6622 1221 13056 4252 3705 7547 7879 1702 3685 4058 2503 7540 9423 4280 12228 574 6265 11876 2711 4805 7605 1468 4802 6921 1954 6350 2733 4429 5862 13549 14543 13809 5357 1509 11478 87 2676 6299 7060 1...
output:
80 1 13153 1 12664 1 2754 1 4425 1 14692 1 4662 1 8044 1 12898 1 14131 1 7206 1 9966 1 4604 1 10801 1 14211 1 9132 1 5731 1 2864 1 10995 1 11626 1 8758 1 13598 1 14166 1 5009 1 5562 1 14061 1 4108 1 10861 1 2470 1 646 1 2033 1 11655 1 9659 1 14058 1 2698 1 150 1 1860 1 13959 1 9764 1 10345 1 84 1 51...
result:
ok OK
Test #15:
score: 0
Accepted
time: 1ms
memory: 7884kb
input:
53 43 32 44 25 10 24 49 20 28 28 44 16 12 37 48 46 36 30 47 25 3 17 31 19 17 29 42 25 44 30 3 31 21 2 34 42 12 22 50 12 52 39 10 0 46 29 1 12 21 3 0 11 31 42 25 4 51 26 36 19 48 39 26 5 21 7 41 29 34 38 47 29 8 26 17 42 46 36 20 39 30 13 27 28 31 27 24
output:
37 1 38 1 47 1 32 1 37 1 48 1 19 1 16 1 1 1 2 1 34 1 8 1 29 1 52 1 5 1 11 17 0 46 36 26 39 10 25 3 30 44 28 20 31 17 21 12 42 1 51 1 4 1 6 1 41 1 7 1 9 1 49 1 24 1 27 1 13 1 14 1 15 1 18 1 50 1 22 1 23 1 33 1 35 1 40 1 43 1 45
result:
ok OK
Test #16:
score: 0
Accepted
time: 1ms
memory: 9948kb
input:
70 21 39 34 29 33 38 53 37 7 47 64 47 17 65 66 60 39 37 47 19 68 14 28 39 41 52 55 0 60 59 16 11 40 11 33 35 26 0 11 24 17 26 43
output:
70 1 34 1 41 1 39 1 60 1 40 1 29 1 33 1 11 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 64 1 24 1 17 1 47 1 37 1 7 1 8 1 9 1 10 1 12 1 13 1 28 1 14 1 15 1 59 1 16 1 18 1 68 1 19 1 20 1 21 1 22 1 23 1 25 1 35 1 43 1 26 1 27 1 30 1 31 1 32 1 36 1 53 1 38 1 42 1 44 1 45 1 46 1 48 1 49 1 50 1 51 1 55 1 52 1 54 1 56 1 ...
result:
ok OK
Test #17:
score: 0
Accepted
time: 1ms
memory: 10024kb
input:
88 139 5 61 52 80 0 17 50 87 62 71 25 69 10 46 44 86 11 38 17 35 73 49 24 47 39 83 8 66 55 56 64 45 83 41 59 35 76 24 2 70 11 77 80 58 84 86 30 50 23 54 36 74 12 10 62 75 33 34 43 28 77 29 10 46 77 33 26 48 32 38 52 79 15 30 25 57 86 0 46 75 81 60 35 83 66 87 25 86 19 85 9 38 15 64 59 82 0 53 40 66 ...
output:
16 1 82 1 45 1 47 1 54 1 68 1 34 1 13 1 74 1 42 1 18 1 12 1 31 1 53 73 0 17 35 59 10 46 75 62 71 56 55 1 9 38 11 77 29 87 50 30 15 64 4 24 76 23 21 2 70 80 52 79 48 26 39 83 41 22 63 19 85 14 6 49 73 33 40 66 8 86 44 58 84 67 25 69 36 27 57 61 5 37 28 43 81 60 20 72 78 3 65 7 32 1 16 1 51
result:
ok OK
Test #18:
score: 0
Accepted
time: 1ms
memory: 9892kb
input:
53 185 48 40 23 7 45 7 6 42 13 6 45 1 18 28 47 14 11 15 27 9 50 44 23 47 20 27 18 19 2 19 18 49 32 49 9 12 11 0 32 49 22 14 8 48 41 28 30 43 4 21 7 22 28 30 17 11 19 30 44 7 46 8 50 45 35 48 29 47 4 26 16 39 37 25 38 12 19 52 28 41 23 31 33 34 6 15 44 24 0 6 26 22 49 43 4 31 20 38 43 39 41 39 51 40 ...
output:
3 16 21 4 26 22 14 47 23 7 45 1 24 44 50 5 29 31 20 0 11 15 6 42 20 27 9 12 38 8 48 40 51 46 10 13 35 17 3 17 2 19 18 28 41 39 16 49 32 43 30 33 34 36 25 37 52
result:
ok OK
Test #19:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
70 252 63 36 64 48 26 34 43 37 30 53 67 64 26 19 25 54 28 44 52 60 4 22 43 48 14 48 12 50 37 23 28 40 48 54 60 23 43 46 7 5 29 39 5 13 57 60 1 23 33 8 59 39 3 29 5 8 34 11 44 40 39 19 40 17 42 48 39 19 49 46 0 48 46 45 57 67 43 60 56 59 32 42 6 54 56 69 23 43 38 65 66 24 0 64 16 10 23 1 4 16 37 49 5...
output:
1 70 0 48 64 67 57 60 52 32 42 51 15 25 54 6 5 7 62 59 39 29 3 34 26 19 68 13 21 9 55 17 40 28 44 66 24 47 16 10 36 63 22 4 65 38 31 27 58 20 11 56 69 61 8 33 35 41 18 30 53 12 50 2 49 46 43 37 23 1 14 45
result:
ok OK
Test #20:
score: 0
Accepted
time: 1ms
memory: 7856kb
input:
88 390 74 40 14 37 44 66 7 49 12 4 39 48 56 76 46 40 80 30 5 39 52 0 40 79 0 11 34 41 43 80 54 62 61 41 54 37 31 81 59 66 23 59 47 84 16 85 68 29 31 63 4 55 27 5 26 68 14 84 16 34 82 16 62 54 46 15 65 63 58 83 5 36 67 19 65 42 35 25 82 73 55 59 28 36 22 38 46 79 61 34 51 40 69 42 36 5 26 38 86 14 22...
output:
3 6 36 5 39 48 60 27 6 20 76 56 9 77 33 76 0 52 75 45 79 40 74 51 15 46 18 70 21 58 83 3 19 67 31 81 65 63 13 8 69 42 10 84 47 78 62 54 37 14 86 7 49 24 50 6 64 28 11 32 25 35 87 82 16 85 41 34 61 57 73 80 30 43 72 1 2 66 44 53 55 4 12 22 38 26 68 29 23 59 71 17
result:
ok OK