QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#317703 | #7999. 拉丁方 | KiharaTouma | 100 ✓ | 1480ms | 170240kb | C++14 | 11.4kb | 2024-01-29 14:52:48 | 2024-01-29 14:52:49 |
Judging History
answer
//qoj7999
#include <bits/stdc++.h>
using namespace std; typedef long long ll; namespace FastIO {
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc() { if (__builtin_expect(_read_ptr == _read_ptr_end, false)) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;} return *_read_ptr++; }
INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } }
INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; inline bool _isdigit(char c) { return (c & 16) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; }
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer; template <class T> INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed; template <class T> INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <> INLINE_V constexpr bool _is_integer<__int128> = true; template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true; template <> INLINE_V constexpr bool _is_signed<__int128> = true; template <> INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
inline void read(char &c) { do c = gc(); while (!_isgraph(c)); } inline void read_cstr(char *s) { char c = gc(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) s.push_back(c), c = gc(); }
template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void read(T &x) { char c = gc(); bool f = true; x = 0; while (!_isdigit(c)) { if (c == 45) f = false; c = gc(); }
if (f) while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); else while (_isdigit(c)) x = x * 10 - (c & 15), c = gc(); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void read(T &x) { char c = gc(); while (!_isdigit(c)) c = gc(); x = 0; while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); }
inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while (*s) pc(*s++); } inline void write(const string &s) { for (char c : s) pc(c); } template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; if (x >= 0) do buffer[digits++] = (x % 10) | 48, x /= 10; while (x);
else { pc(45); do buffer[digits++] = -(x % 10) | 48, x /= 10; while (x); } while (digits) pc(buffer[--digits]); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; do buffer[digits++] = (x % 10) | 48, x /= 10; while (x); while (digits) pc(buffer[--digits]); }
template <int N> struct _tuple_io_helper { template <class... T> static inline void _read(tuple<T...> &x) { _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x)); } };
template <> struct _tuple_io_helper<1> { template <class... T> static inline void _read(tuple<T...> &x) { read(get<0>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { write(get<0>(x)); } };
template <class... T> inline void read(tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_read(x); } template <class... T> inline void write(const tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_write(x); }
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); } template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first), pc(32), write(x.second); }
template <class T1, class... T2> inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template <class... T> inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template <class T1, class... T2> inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template <class... T> inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template <class T> inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template <class T1, class... T2> inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template <class... T> inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template <class... T> inline void println(const T &...x) { print(x...), pc(10); } template <class... T> inline void printk(const T &...x) { print(x...), pc(32); } template <class... T> inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; void solve();int main(){ solve(); return 0; }
const int N = 510;
int T, n, r, c, a[N][N], flg, vs[N][N], ind[N*2], cnt[N], nw[N*2];
struct Graph{
int hd[N*2], dep[N*2], now[N*2], tot = 1;
struct edge{
int eg, ln, nx, ban;
} eg[N*N*5];
void add(int u, int v, int w){
eg[++tot] = { v, w, hd[u], 0 };
hd[u] = tot;
}
bool bfs(int s, int t){
memset(dep, 0, sizeof(dep));
memcpy(now, hd, sizeof(hd));
dep[s] = 1;
queue<int> q;
q.push(s);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = hd[x]; i; i = eg[i].nx){
int y = eg[i].eg, z = eg[i].ln;
if(!dep[y] && z && !eg[i].ban){
dep[y] = dep[x] + 1;
q.push(y);
if(y == t){
return 1;
}
}
}
}
return 0;
}
int dfs(int x, int t, int fl){
if(x == t){
return fl;
}
int rs = fl;
for(int i = now[x]; i && rs; i = eg[i].nx){
int y = eg[i].eg, z = eg[i].ln;
now[x] = i;
if(dep[y] == dep[x] + 1 && z && !eg[i].ban){
int k = dfs(y, t, min(z, rs));
if(!k){
dep[y] = 0;
}
eg[i].ln -= k;
eg[i^1].ln += k;
rs -= k;
}
}
return fl - rs;
}
int dinic(int s, int t){
int mf = 0, tmp = 0;
while(bfs(s, t)){
while(tmp = dfs(s, t, 1000)){
mf += tmp;
}
}
return mf;
}
void init(){
tot = 1;
memset(hd, 0, sizeof(hd));
}
int fl(){
for(int i = 1; i <= n; ++ i){
add(0, i, 1);
add(i, 0, 0);
add(i+n, n+n+1, 1);
add(n+n+1, i+n, 0);
}
return dinic(0, n+n+1);
}
} g, G[60];
void eular(int d, int deg){
memset(ind, 0, sizeof(ind));
memcpy(nw, G[d].hd, sizeof(nw));
for(int i = 1; i <= n+n; ++ i){
ind[i] = deg;
}
queue<int> q;
for(int i = 1; i <= n; ++ i){
if(ind[i]){
q.push(i);
int cl = 2;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = nw[x]; i; i = G[d].eg[i].nx){
nw[x] = i;
int y = G[d].eg[i].eg;
bool chk = (x < y) ? G[d].eg[i].ln : !G[d].eg[i].ln;
if(y != 0 && y != n+n+1 && ind[y] && chk && !G[d].eg[i].ban){
-- ind[x];
G[d].eg[i].ban = G[d].eg[i^1].ban = cl;
cl = 5 - cl;
q.push(y);
break;
}
}
}
}
}
}
void pp1(int l, int r, int d){
if(l == r){
for(int j = 1; j <= n; ++ j){
for(int k = G[d].hd[j]; k; k = G[d].eg[k].nx){
if(G[d].eg[k].eg > n && !G[d].eg[k].ban){
a[G[d].eg[k].eg-n][l] = j;
G[d].eg[k].ban = G[d].eg[k^1].ban = 1;
}
}
}
return;
}
if((r - l + 1) & 1){
int i = l;
G[d].fl();
for(int j = 1; j <= n; ++ j){
for(int k = G[d].hd[j]; k; k = G[d].eg[k].nx){
if(G[d].eg[k].eg > n && !G[d].eg[k].ln && !G[d].eg[k].ban){
a[G[d].eg[k].eg-n][i] = j;
G[d].eg[k].ban = G[d].eg[k^1].ban = 1;
}
}
}
++ l;
}
int mid = l + r >> 1;
eular(d, r-l+1);
G[d+2].init();
G[d+3].init();
for(int x = 1; x <= n; ++ x){
for(int j = G[d].hd[x]; j; j = G[d].eg[j].nx){
int y = G[d].eg[j].eg;
if(G[d].eg[j].ban == 3){
G[d+2].add(x, y, 1);
G[d+2].add(y, x, 0);
} else if(G[d].eg[j].ban == 2){
G[d+3].add(x, y, 1);
G[d+3].add(y, x, 0);
}
}
}
pp1(l, mid, d+2);
pp1(mid+1, r, d+3);
}
void pr1(){
G[0].init();
memset(vs, 0, sizeof(vs));
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= r; ++ i){
for(int j = 1; j <= c; ++ j){
vs[a[i][j]][i] = 1;
++ cnt[a[i][j]];
}
}
for(int i = 1; i <= n; ++ i){
cnt[i] = r - cnt[i];
if(cnt[i] > n-c){
flg = 0;
return;
}
for(int j = 1; j <= r; ++ j){
if(!vs[i][j]){
G[0].add(i, j+n, 1);
G[0].add(j+n, i, 0);
}
}
}
for(int i = r + 1, nw = 1; i <= n; ++ i){
for(int j = 1; j <= n-c; ++ j){
while(cnt[nw] == n - c){
++ nw;
}
G[0].add(nw, i+n, 1);
G[0].add(i+n, nw, 0);
++ cnt[nw];
}
}
pp1(c+1, n, 0);
}
void pp2(int l, int r, int d){
if(l == r){
for(int j = 1; j <= n; ++ j){
for(int k = G[d].hd[j]; k; k = G[d].eg[k].nx){
if(G[d].eg[k].eg > n && !G[d].eg[k].ban){
a[l][G[d].eg[k].eg-n] = j;
G[d].eg[k].ban = G[d].eg[k^1].ban = 1;
}
}
}
return;
}
if((r - l + 1) & 1){
int i = l;
G[d].fl();
for(int j = 1; j <= n; ++ j){
for(int k = G[d].hd[j]; k; k = G[d].eg[k].nx){
if(G[d].eg[k].eg > n && !G[d].eg[k].ln && !G[d].eg[k].ban){
a[i][G[d].eg[k].eg-n] = j;
G[d].eg[k].ban = G[d].eg[k^1].ban = 1;
}
}
}
++ l;
}
if(l > r){
return;
}
int mid = l + r >> 1;
eular(d, r-l+1);
G[d+2].init();
G[d+3].init();
for(int x = 1; x <= n; ++ x){
for(int j = G[d].hd[x]; j; j = G[d].eg[j].nx){
int y = G[d].eg[j].eg;
if(G[d].eg[j].ban == 3){
G[d+2].add(x, y, 1);
G[d+2].add(y, x, 0);
} else if(G[d].eg[j].ban == 2){
G[d+3].add(x, y, 1);
G[d+3].add(y, x, 0);
}
}
}
pp2(l, mid, d+2);
pp2(mid+1, r, d+3);
}
void pr2(){
static int vs[N][N];
G[1].init();
memset(vs, 0, sizeof(vs));
for(int i = 1; i <= r; ++ i){
for(int j = 1; j <= n; ++ j){
vs[a[i][j]][j] = 1;
}
}
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j){
if(!vs[i][j]){
G[1].add(i, j+n, 1);
G[1].add(j+n, i, 0);
}
}
}
pp2(r+1, n, 1);
}
void solve(){
read(T);
while(T--){
read(n, r, c);
flg = 1;
for(int i = 1; i <= r; ++ i){
for(int j = 1; j <= c; ++ j){
read(a[i][j]);
}
}
if(c < n){
pr1();
}
if(flg){
pr2();
println_cstr("Yes");
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j){
printk(a[i][j]);
}
print('\n');
}
} else {
println_cstr("No");
}
}
}
詳細信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 131464kb
input:
10 6 2 1 1 3 6 2 4 1 4 2 6 6 5 4 3 6 4 4 4 1 5 3 5 2 1 6 6 3 2 4 2 6 3 5 6 6 3 4 5 1 1 2 4 3 6 2 2 4 6 6 3 5 5 1 3 6 1 2 4 3 6 2 2 5 2 3 1 6 2 1 5 3 6 4 6 1 6 2 4 3 5 4 2 3 5 1 6 3 5 1 6 4 2 6 3 4 2 5 1 6 1 4 2 6 1 5 6 3 4 3 1 2 4 4 3 5 2 2 5 4 1
output:
Yes 1 2 3 6 4 5 3 4 5 1 6 2 6 5 2 4 1 3 2 1 4 3 5 6 4 3 6 5 2 1 5 6 1 2 3 4 Yes 1 4 2 6 3 5 6 5 4 3 1 2 5 3 1 2 4 6 2 1 6 4 5 3 4 6 3 5 2 1 3 2 5 1 6 4 Yes 4 1 5 3 6 2 5 2 1 6 3 4 6 3 2 4 1 5 2 6 3 5 4 1 1 4 6 2 5 3 3 5 4 1 2 6 Yes 4 5 1 2 3 6 1 2 4 3 6 5 3 6 2 1 5 4 2 4 6 5 1 3...
result:
ok ok (10 test cases)
Test #2:
score: 5
Accepted
time: 0ms
memory: 129604kb
input:
10 6 2 1 5 4 6 4 1 3 1 2 6 6 1 4 6 4 2 3 6 4 2 2 5 4 1 6 3 3 2 6 2 4 4 6 2 3 2 5 4 1 6 2 2 3 5 1 2 6 3 2 6 2 5 3 1 4 6 3 2 5 3 1 4 6 2 6 5 2 5 1 2 6 3 4 1 2 6 5 6 3 4 5 1 4 2 4 5 3 1 3 2 1 5
output:
Yes 5 1 2 6 3 4 4 3 5 1 6 2 3 2 1 4 5 6 1 6 4 5 2 3 6 5 3 2 4 1 2 4 6 3 1 5 Yes 3 1 4 6 2 5 1 2 3 5 4 6 2 4 5 1 6 3 6 5 2 4 3 1 4 6 1 3 5 2 5 3 6 2 1 4 Yes 6 4 2 3 1 5 1 2 3 4 5 6 4 5 1 2 6 3 3 1 6 5 2 4 2 3 5 6 4 1 5 6 4 1 3 2 Yes 2 5 4 1 3 6 4 1 3 6 2 5 6 3 5 2 4 1 3 2 1 5 6 4...
result:
ok ok (10 test cases)
Test #3:
score: 5
Accepted
time: 0ms
memory: 131644kb
input:
10 10 7 7 1 7 5 10 2 3 4 5 2 4 9 6 8 10 3 10 1 6 4 7 5 4 8 2 7 1 9 3 9 6 3 8 10 5 1 7 4 9 3 5 1 6 6 3 10 1 8 2 9 10 3 9 8 7 2 9 3 6 10 1 5 1 3 7 5 10 9 6 4 2 2 6 8 10 1 4 5 9 7 10 1 7 5 10 3 6 2 8 7 10 3 7 8 1 7 9 3 4 10 5 10 1 8 7 2 3 9 3 2 4 6 10 5 10 1 3 2 7 8 10 1 8 6 4 2 10 5 8 3 1 10 9 9 2 5 4...
output:
Yes 1 7 5 10 2 3 4 8 6 9 5 2 4 9 6 8 10 1 3 7 3 10 1 6 4 7 5 9 2 8 4 8 2 7 1 9 3 6 10 5 9 6 3 8 10 5 1 4 7 2 7 4 9 3 5 1 6 2 8 10 6 3 10 1 8 2 9 7 5 4 2 1 6 5 7 4 8 10 9 3 8 9 7 4 3 10 2 5 1 6 10 5 8 2 9 6 7 3 4 1 Yes 8 7 2 9 3 6 10 1 5 4 1 3 7 5 10 9 6 4 2 8 2 6 8 10 1 4 5 9 7 3 10 2 3...
result:
ok ok (10 test cases)
Test #4:
score: 5
Accepted
time: 0ms
memory: 130872kb
input:
10 10 1 1 10 10 8 8 1 7 5 2 3 6 4 10 2 3 4 7 9 8 5 6 9 8 6 10 1 5 2 3 5 10 3 9 4 7 1 8 4 6 1 8 10 2 7 9 7 5 9 4 2 3 8 1 3 2 7 6 5 10 9 4 10 9 8 1 6 4 3 5 10 4 7 10 7 5 3 6 9 4 3 8 7 9 1 4 10 6 5 4 1 10 2 3 2 4 10 8 7 5 6 10 5 2 6 7 4 2 9 5 3 10 8 1 10 4 7 9 6 5 1 4 2 10 7 4 2 8 10 5 3 10 1 3 9 7 8 5...
output:
Yes 10 1 4 8 2 6 5 9 3 7 1 2 3 4 6 5 7 8 9 10 6 3 10 5 8 9 1 2 7 4 2 9 8 7 4 3 10 5 1 6 4 5 1 9 10 7 6 3 8 2 8 7 6 3 1 2 4 10 5 9 3 4 2 10 9 1 8 7 6 5 9 8 7 6 5 10 3 4 2 1 5 10 9 1 7 8 2 6 4 3 7 6 5 2 3 4 9 1 10 8 Yes 1 7 5 2 3 6 4 10 9 8 2 3 4 7 9 8 5 6 1 10 9 8 6 10 1 5 2 3 7 4 5 10 3...
result:
ok ok (10 test cases)
Test #5:
score: 5
Accepted
time: 1480ms
memory: 159716kb
input:
10 500 1 39 201 443 328 346 404 472 146 117 171 389 321 403 420 280 197 343 126 315 108 39 42 278 303 11 255 330 101 422 263 281 496 110 97 159 406 241 178 187 179 500 1 362 278 200 441 177 47 404 184 261 199 492 198 470 39 71 297 72 134 157 92 313 269 40 304 168 447 290 224 181 481 218 489 374 383 ...
output:
Yes 201 443 328 346 404 472 146 117 171 389 321 403 420 280 197 343 126 315 108 39 42 278 303 11 255 330 101 422 263 281 496 110 97 159 406 241 178 187 179 1 4 8 59 129 410 268 200 478 340 25 91 374 233 163 445 304 75 145 428 287 217 494 358 43 111 391 250 182 461 322 51 120 399 259 191 469 332 17 8...
result:
ok ok (10 test cases)
Test #6:
score: 5
Accepted
time: 11ms
memory: 133816kb
input:
10 100 59 100 89 11 52 81 39 8 35 20 63 73 96 13 7 78 67 46 6 51 90 27 25 68 5 40 44 70 38 36 19 10 54 3 91 56 1 86 82 15 74 71 66 48 16 75 21 29 55 77 61 95 60 57 30 53 4 9 99 22 65 2 47 17 24 23 59 62 28 97 87 43 79 98 41 33 14 64 45 69 50 93 26 88 34 49 100 84 72 37 80 58 94 92 12 42 76 85 83 18 ...
output:
Yes 89 11 52 81 39 8 35 20 63 73 96 13 7 78 67 46 6 51 90 27 25 68 5 40 44 70 38 36 19 10 54 3 91 56 1 86 82 15 74 71 66 48 16 75 21 29 55 77 61 95 60 57 30 53 4 9 99 22 65 2 47 17 24 23 59 62 28 97 87 43 79 98 41 33 14 64 45 69 50 93 26 88 34 49 100 84 72 37 80 58 94 92 12 42 76 85 83 18 32 31 45 ...
result:
ok ok (10 test cases)
Test #7:
score: 5
Accepted
time: 11ms
memory: 132020kb
input:
10 100 87 100 1 86 29 33 80 26 57 15 60 2 52 93 100 56 32 4 96 34 85 91 43 72 19 83 16 75 39 35 64 31 82 74 36 17 14 25 63 58 54 18 22 13 94 73 98 37 68 30 20 41 10 95 45 42 61 38 78 12 49 55 84 3 53 7 81 40 47 66 92 76 59 6 79 99 89 70 77 23 62 97 28 24 44 67 88 5 46 8 9 87 27 11 65 69 21 51 71 48 ...
output:
Yes 1 86 29 33 80 26 57 15 60 2 52 93 100 56 32 4 96 34 85 91 43 72 19 83 16 75 39 35 64 31 82 74 36 17 14 25 63 58 54 18 22 13 94 73 98 37 68 30 20 41 10 95 45 42 61 38 78 12 49 55 84 3 53 7 81 40 47 66 92 76 59 6 79 99 89 70 77 23 62 97 28 24 44 67 88 5 46 8 9 87 27 11 65 69 21 51 71 48 90 50 63 ...
result:
ok ok (10 test cases)
Test #8:
score: 5
Accepted
time: 130ms
memory: 138668kb
input:
10 300 115 300 258 235 113 48 246 149 278 25 90 216 220 299 69 285 134 206 39 52 15 265 111 28 94 11 194 187 242 154 62 60 116 135 86 144 124 108 119 283 282 211 245 295 112 261 4 2 10 244 267 196 83 143 105 70 40 272 55 155 97 74 13 65 132 288 170 174 260 165 46 151 252 53 32 201 66 142 274 27 30 1...
output:
Yes 258 235 113 48 246 149 278 25 90 216 220 299 69 285 134 206 39 52 15 265 111 28 94 11 194 187 242 154 62 60 116 135 86 144 124 108 119 283 282 211 245 295 112 261 4 2 10 244 267 196 83 143 105 70 40 272 55 155 97 74 13 65 132 288 170 174 260 165 46 151 252 53 32 201 66 142 274 27 30 197 96 98 19...
result:
ok ok (10 test cases)
Test #9:
score: 5
Accepted
time: 179ms
memory: 141572kb
input:
10 300 39 300 153 47 152 270 96 202 24 212 109 69 160 116 133 91 150 258 246 8 295 210 223 99 178 159 32 205 101 23 213 26 89 281 117 218 106 75 215 290 104 82 113 105 174 71 297 242 197 115 221 225 5 122 286 94 9 200 28 203 33 77 108 234 12 279 7 34 154 229 62 143 186 142 275 168 196 111 25 51 156 ...
output:
Yes 153 47 152 270 96 202 24 212 109 69 160 116 133 91 150 258 246 8 295 210 223 99 178 159 32 205 101 23 213 26 89 281 117 218 106 75 215 290 104 82 113 105 174 71 297 242 197 115 221 225 5 122 286 94 9 200 28 203 33 77 108 234 12 279 7 34 154 229 62 143 186 142 275 168 196 111 25 51 156 228 193 4 ...
result:
ok ok (10 test cases)
Test #10:
score: 5
Accepted
time: 441ms
memory: 156764kb
input:
10 500 18 500 282 102 421 339 20 225 141 221 457 330 196 314 245 377 7 39 113 106 111 57 495 479 480 388 405 367 398 112 101 379 251 255 208 75 4 66 392 284 93 395 86 231 96 125 368 448 149 400 322 427 378 199 97 474 477 100 85 45 258 138 281 273 363 202 288 493 328 483 357 190 194 43 289 19 319 137...
output:
Yes 282 102 421 339 20 225 141 221 457 330 196 314 245 377 7 39 113 106 111 57 495 479 480 388 405 367 398 112 101 379 251 255 208 75 4 66 392 284 93 395 86 231 96 125 368 448 149 400 322 427 378 199 97 474 477 100 85 45 258 138 281 273 363 202 288 493 328 483 357 190 194 43 289 19 319 137 404 209 2...
result:
ok ok (10 test cases)
Test #11:
score: 5
Accepted
time: 1363ms
memory: 170240kb
input:
10 500 171 146 271 474 337 28 15 9 494 482 381 404 25 74 465 378 446 11 150 160 434 199 248 419 221 354 425 265 215 94 426 197 288 287 236 223 259 8 167 453 284 499 483 473 171 62 464 383 2 476 313 116 394 293 212 182 347 457 108 325 95 82 396 96 254 432 90 79 247 351 303 110 54 459 460 311 158 415 ...
output:
Yes 271 474 337 28 15 9 494 482 381 404 25 74 465 378 446 11 150 160 434 199 248 419 221 354 425 265 215 94 426 197 288 287 236 223 259 8 167 453 284 499 483 473 171 62 464 383 2 476 313 116 394 293 212 182 347 457 108 325 95 82 396 96 254 432 90 79 247 351 303 110 54 459 460 311 158 415 469 149 268...
result:
ok ok (10 test cases)
Test #12:
score: 5
Accepted
time: 1337ms
memory: 166148kb
input:
10 500 61 70 15 300 446 146 477 420 244 462 443 49 328 24 158 440 47 18 43 388 258 366 488 312 426 138 359 114 489 130 464 407 190 450 471 391 55 89 345 131 393 247 39 265 196 78 299 384 135 219 179 184 313 406 73 424 193 459 291 343 434 58 427 92 295 441 83 285 87 397 499 493 494 55 314 100 383 7 3...
output:
Yes 15 300 446 146 477 420 244 462 443 49 328 24 158 440 47 18 43 388 258 366 488 312 426 138 359 114 489 130 464 407 190 450 471 391 55 89 345 131 393 247 39 265 196 78 299 384 135 219 179 184 313 406 73 424 193 459 291 343 434 58 427 92 295 441 83 285 87 397 499 493 435 353 304 115 421 239 77 283 ...
result:
ok ok (10 test cases)
Test #13:
score: 5
Accepted
time: 19ms
memory: 130212kb
input:
10 100 55 94 8 91 69 56 99 10 29 79 49 39 40 78 57 26 35 28 92 45 66 51 15 82 44 9 41 60 18 67 11 81 90 27 2 36 34 59 73 23 20 95 58 3 22 84 54 87 16 63 52 88 38 80 55 1 96 14 24 17 89 21 83 53 64 71 30 85 98 74 25 31 46 70 94 13 77 86 93 61 6 7 75 19 62 42 4 33 47 50 100 48 5 32 97 68 25 10 39 68 5...
output:
Yes 8 91 69 56 99 10 29 79 49 39 40 78 57 26 35 28 92 45 66 51 15 82 44 9 41 60 18 67 11 81 90 27 2 36 34 59 73 23 20 95 58 3 22 84 54 87 16 63 52 88 38 80 55 1 96 14 24 17 89 21 83 53 64 71 30 85 98 74 25 31 46 70 94 13 77 86 93 61 6 7 75 19 62 42 4 33 47 50 100 48 5 32 97 68 65 12 76 72 43 37 25 ...
result:
ok ok (10 test cases)
Test #14:
score: 5
Accepted
time: 20ms
memory: 135196kb
input:
10 100 4 18 31 65 89 37 67 58 8 48 40 92 12 68 15 98 88 29 43 24 16 30 49 22 4 66 98 81 34 79 8 85 53 23 77 12 67 95 62 48 44 5 69 25 74 68 87 21 99 50 94 82 64 57 19 33 84 40 32 76 52 18 61 28 26 60 83 59 41 11 10 46 91 78 100 92 87 48 8 18 45 5 89 75 79 96 19 41 53 73 42 36 46 94 31 69 20 98 13 83...
output:
Yes 31 65 89 37 67 58 8 48 40 92 12 68 15 98 88 29 43 24 25 54 5 83 23 64 57 36 75 94 16 7 87 41 71 46 80 60 33 100 18 77 51 30 91 10 1 81 44 20 62 13 97 38 73 69 27 86 3 56 49 76 32 11 72 55 95 26 61 2 45 84 78 39 53 99 21 6 19 85 66 47 28 14 63 42 93 34 74 4 59 82 79 17 90 22 50 52 96 9 70 35 16 ...
result:
ok ok (10 test cases)
Test #15:
score: 5
Accepted
time: 213ms
memory: 145600kb
input:
10 300 44 46 113 257 78 212 276 158 253 150 210 278 127 237 40 149 30 63 294 143 239 49 231 70 176 111 213 203 256 192 35 69 68 250 21 23 94 41 288 171 65 126 236 44 289 137 53 129 290 230 271 87 84 251 243 127 279 48 14 174 17 194 191 154 228 297 3 82 86 195 278 143 98 241 137 20 239 30 224 100 169...
output:
Yes 113 257 78 212 276 158 253 150 210 278 127 237 40 149 30 63 294 143 239 49 231 70 176 111 213 203 256 192 35 69 68 250 21 23 94 41 288 171 65 126 236 44 289 137 53 129 233 205 295 199 43 159 3 235 275 117 104 179 82 19 267 141 60 216 152 125 90 56 290 17 201 224 258 73 184 252 112 177 32 9 247 5...
result:
ok ok (10 test cases)
Test #16:
score: 5
Accepted
time: 286ms
memory: 149984kb
input:
10 300 188 74 150 99 240 206 215 91 127 278 69 254 229 266 211 180 205 183 270 198 261 1 48 258 231 148 280 159 21 225 237 109 54 196 77 284 89 189 233 247 217 257 193 291 42 221 213 15 163 14 121 245 26 66 52 218 166 236 139 62 103 242 182 101 234 174 288 59 300 111 144 223 72 216 9 41 10 278 32 19...
output:
Yes 150 99 240 206 215 91 127 278 69 254 229 266 211 180 205 183 270 198 261 1 48 258 231 148 280 159 21 225 237 109 54 196 77 284 89 189 233 247 217 257 193 291 42 221 213 15 163 14 121 245 26 66 52 218 166 236 139 62 103 242 182 101 234 174 288 59 300 111 144 223 72 216 9 41 107 98 131 56 283 4 20...
result:
ok ok (10 test cases)
Test #17:
score: 5
Accepted
time: 861ms
memory: 164128kb
input:
10 500 137 394 193 219 137 113 369 248 464 74 408 167 383 399 482 149 154 147 6 50 69 440 437 29 286 427 307 141 228 373 296 244 273 428 44 266 341 173 255 487 114 332 416 405 367 312 323 163 133 339 20 170 26 67 96 195 241 14 205 233 291 179 478 235 381 151 185 469 82 473 441 421 311 118 350 404 23...
output:
Yes 193 219 137 113 369 248 464 74 408 167 383 399 482 149 154 147 6 50 69 440 437 29 286 427 307 141 228 373 296 244 273 428 44 266 341 173 255 487 114 332 416 405 367 312 323 163 133 339 20 170 26 67 96 195 241 14 205 233 291 179 478 235 381 151 185 469 82 473 441 421 311 118 350 404 230 218 472 3...
result:
ok ok (10 test cases)
Test #18:
score: 5
Accepted
time: 988ms
memory: 166356kb
input:
10 500 481 22 422 263 216 135 73 497 183 188 119 498 338 39 111 113 469 372 274 348 15 456 459 82 21 98 209 76 360 5 481 198 153 147 138 278 131 330 270 350 293 492 426 95 468 27 225 47 65 467 473 440 279 352 475 248 17 33 456 210 70 421 55 208 46 464 277 314 15 426 427 25 300 30 150 417 306 448 492...
output:
Yes 422 263 216 135 73 497 183 188 119 498 338 39 111 113 469 372 274 348 15 456 459 82 499 3 494 489 26 345 87 212 417 313 203 108 403 301 67 441 154 250 16 433 295 95 391 176 258 134 362 236 43 468 336 182 33 100 411 222 282 457 290 57 370 355 166 162 479 228 78 11 117 437 244 395 199 329 55 271 1...
result:
ok ok (10 test cases)
Test #19:
score: 5
Accepted
time: 863ms
memory: 166112kb
input:
10 500 30 446 375 376 479 293 237 104 108 215 262 4 444 241 436 121 443 195 50 166 234 165 285 315 412 469 92 159 302 44 252 9 392 487 3 495 28 96 341 253 466 352 365 32 176 401 483 60 247 8 58 371 143 68 158 201 364 42 381 240 22 272 427 183 306 235 66 144 438 138 437 208 52 122 174 209 15 102 445 ...
output:
Yes 375 376 479 293 237 104 108 215 262 4 444 241 436 121 443 195 50 166 234 165 285 315 412 469 92 159 302 44 252 9 392 487 3 495 28 96 341 253 466 352 365 32 176 401 483 60 247 8 58 371 143 68 158 201 364 42 381 240 22 272 427 183 306 235 66 144 438 138 437 208 52 122 174 209 15 102 445 428 465 85...
result:
ok ok (10 test cases)
Test #20:
score: 5
Accepted
time: 814ms
memory: 157948kb
input:
10 500 204 440 401 43 120 246 337 382 241 103 329 272 343 439 9 435 159 355 468 281 333 54 158 479 106 88 50 288 204 412 317 70 78 446 121 238 458 338 230 239 313 263 237 249 115 27 56 107 282 132 117 74 32 113 84 105 413 102 371 184 12 148 373 262 83 29 283 331 209 134 125 67 60 147 459 82 270 316 ...
output:
Yes 401 43 120 246 337 382 241 103 329 272 343 439 9 435 159 355 468 281 333 54 158 479 106 88 50 288 204 412 317 70 78 446 121 238 458 338 230 239 313 263 237 249 115 27 56 107 282 132 117 74 32 113 84 105 413 102 371 184 12 148 373 262 83 29 283 331 209 134 125 67 60 147 459 82 270 316 244 3 4 28 ...
result:
ok ok (10 test cases)