QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#570817#9319. Bull FarmsubcripAC ✓671ms51260kbC++1721.5kb2024-09-17 18:04:432024-09-17 18:04:43

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 18:04:43]
  • 评测
  • 测评结果:AC
  • 用时:671ms
  • 内存:51260kb
  • [2024-09-17 18:04:43]
  • 提交

answer

// #pragma GCC target("popcnt,lzcnt,abm,bmi,bmi2")
#pragma GCC optimize("Ofast")
/************* This code requires C++17. ***************/

#include<bits/stdc++.h>
using namespace std;

/* macro helpers */
#define __NARGS(...) std::tuple_size<decltype(std::make_tuple(__VA_ARGS__))>::value
#define __DECOMPOSE_S(a, x) auto x = a;
#define __DECOMPOSE_N(a, ...) auto [__VA_ARGS__] = a;
constexpr void __() {}
#define __AS_PROCEDURE(...) __(); __VA_ARGS__; __()
#define __as_typeof(container) remove_reference<decltype(container)>::type

/* type aliases */
#if LONG_LONG_MAX != INT64_MAX
using ll = int64_t;
using ull = uint64_t;
#else
using ll = long long;
using ull = unsigned long long;
#endif
using int128 = __int128_t;
using uint128 = __uint128_t;
using ld = long double;
using pii = pair<int, int>;           using pil = pair<int, ll>;           using pid = pair<int, ld>;
using pli = pair<ll, int>;            using pll = pair<ll, ll>;            using pld = pair<ll, ld>;
using pdi = pair<ld, int>;            using pdl = pair<ld, ll>;            using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;    using tiil = tuple<int, int, ll>;    using tiid = tuple<int, int, ld>;
using tili = tuple<int, ll, int>;     using till = tuple<int, ll, ll>;     using tild = tuple<int, ll, ld>;
using tidi = tuple<int, ld, int>;     using tidl = tuple<int, ld, ll>;     using tidd = tuple<int, ld, ld>;
using tlii = tuple<ll, int, int>;     using tlil = tuple<ll, int, ll>;     using tlid = tuple<ll, int, ld>;
using tlli = tuple<ll, ll, int>;      using tlll = tuple<ll, ll, ll>;      using tlld = tuple<ll, ll, ld>;
using tldi = tuple<ll, ld, int>;      using tldl = tuple<ll, ld, ll>;      using tldd = tuple<ll, ld, ld>;
using tdii = tuple<ld, int, int>;     using tdil = tuple<ld, int, ll>;     using tdid = tuple<ld, int, ld>;
using tdli = tuple<ld, ll, int>;      using tdll = tuple<ld, ll, ll>;      using tdld = tuple<ld, ll, ld>;
using tddi = tuple<ld, ld, int>;      using tddl = tuple<ld, ld, ll>;      using tddd = tuple<ld, ld, ld>;
template <typename T> using max_heap = priority_queue<T>;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<>>;
template <typename T> using oi = ostream_iterator<T>;
template <typename T> using ii = istream_iterator<T>;

/* constants */
constexpr int INF = 0x3f3f3f3f;
constexpr ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
constexpr ll MDL = 1e9 + 7;
constexpr ll PRIME = 998'244'353;
constexpr ll MDL1 = 8784491;
constexpr ll MDL2 = PRIME;
constexpr int128 INT128_MAX = numeric_limits<int128>::max();
constexpr uint128 UINT128_MAX = numeric_limits<uint128>::max();
constexpr int128 INT128_MIN = numeric_limits<int128>::min();
constexpr uint128 UINT128_MIN = numeric_limits<uint128>::min();

/* random */

mt19937_64 rd(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());

/* bit-wise operations */
#define lowbit(x) ((x) & -(x))
#define popcount(x) (__builtin_popcountll(ll(x)))
#define parity(x) (__builtin_parityll(ll(x)))
#define msp(x) (63LL - __builtin_clzll(ll(x)))
#define lsp(x) (__builtin_ctzll(ll(x)))

/* arithmetic operations */
#define mod(x, y) ((((x) % (y)) + (y)) % (y))

/* fast pairs */
#define upair ull
#define umake(x, y) (ull(x) << 32 | (ull(y) & ((1ULL << 32) - 1)))
#define u1(p) ((p) >> 32)
#define u2(p) ((p) & ((1ULL << 32) - 1))
#define ult std::less<upair>
#define ugt std::greater<upair>

#define ipair ull
#define imake(x, y) (umake(x, y))
#define i1(p) (int(u1(ll(p))))
#define i2(p) (ll(u2(p) << 32) >> 32)
struct ilt {
    bool operator()(const ipair& a, const ipair& b) const {
        if (i1(a) == i1(b)) return i2(a) < i2(b);
        else return i1(a) < i1(b);
    }
};
struct igt {
    bool operator()(const ipair& a, const ipair& b) const {
        if (i1(a) == i1(b)) return i2(a) > i2(b);
        else return i1(a) > i1(b);
    }
};

/* conditions */
#define loop while (1)
#define if_or(var, val) if (!(var == val)) var = val; else
#define continue_or(var, val) __AS_PROCEDURE(if (var == val) continue; var = val;)
#define break_or(var, val) __AS_PROCEDURE(if (var == val) break; var = val;)

/* hash */
struct safe_hash {
    // https://codeforces.com/blog/entry/62393
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash {
    template <typename T, typename U>
    size_t operator()(const pair<T, U>& a) const {
        auto hash1 = safe_hash()(a.first);
        auto hash2 = safe_hash()(a.second);
        if (hash1 != hash2) {
            return hash1 ^ hash2;
        }
        return hash1;
    }
};

uniform_int_distribution<mt19937::result_type> dist(PRIME);
const size_t __array_hash_b = 31, __array_hash_mdl1 = dist(rd), __array_hash_mdl2 = dist(rd);
struct array_hash {
    template <typename Sequence>
    size_t operator()(const Sequence& arr) const {
        size_t pw1 = 1, pw2 = 1;
        size_t res1 = 0, res2 = 0;
        for (auto&& x : arr) {
            res1 = (res1 + x * pw1) % __array_hash_mdl1;
            res2 = (res2 + x * pw2) % __array_hash_mdl2;
            pw1 = (pw1 * __array_hash_b) % __array_hash_mdl1;
            pw2 = (pw2 * __array_hash_b) % __array_hash_mdl2;
        }
        return res1 + res2;
    }
};

/* build data structures */
#define faster(um) __AS_PROCEDURE((um).reserve(1024); (um).max_load_factor(0.25);)
#define unordered_counter(from, to) __AS_PROCEDURE(unordered_map<__as_typeof(from), size_t, safe_hash> to; for (auto&& x : from) ++to[x];)
#define counter(from, to, cmp) __AS_PROCEDURE(map<__as_typeof(from), size_t, cmp> to; for (auto&& x : from) ++to[x];)
#define pa(a) __AS_PROCEDURE(__typeof(a) pa; pa.push_back({}); for (auto&&x : a) pa.push_back(pa.back() + x);)
#define sa(a) __AS_PROCEDURE(__typeof(a) sa(a.size() + 1); {int n = a.size(); for (int i = n - 1; i >= 0; --i) sa[i] = sa[i + 1] + a[i];};)
#define adj(ch, n) __AS_PROCEDURE(vector<vector<int>> ch((n) + 1);)
#define edge(ch, u, v) __AS_PROCEDURE(ch[u].push_back(v), ch[v].push_back(u);)
#define edgew(ch, u, v, ...) __AS_PROCEDURE(ch[u].emplace_back(v, __VA_ARGS__), ch[v].emplace_back(u, __VA_ARGS__);)
#define Edge(ch, u, v) __AS_PROCEDURE(ch[u].push_back(v);)
#define Edgew(ch, u, v, ...) __AS_PROCEDURE(ch[u].emplace_back(v, __VA_ARGS__);)
template <typename T, typename Iterator> pair<size_t, map<T, size_t>> discretize(Iterator __first, Iterator __last) {
    set<T> st(__first, __last);
    size_t N = 0;
    map<T, size_t> mp;
    for (auto&& x : st) mp[x] = ++N;
    return {N, mp};
}
template <typename T, typename Iterator> pair<size_t, unordered_map<T, size_t, safe_hash>> unordered_discretize(Iterator __first, Iterator __last) {
    set<T> st(__first, __last);
    size_t N = 0;
    unordered_map<T, size_t, safe_hash> mp;
    for (auto&& x : st) mp[x] = ++N;
    return {N, mp};
}

/* io */
#define untie __AS_PROCEDURE(ios_base::sync_with_stdio(0), cin.tie(NULL))
template<typename T, typename U> istream& operator>>(istream& in, pair<T, U>& p) {
    return in >> p.first >> p.second;
}
template<typename T, typename U> ostream& operator<<(ostream& out, const pair<T, U>& p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
}
template<typename Char, typename Traits, typename Tuple, std::size_t... Index>
void print_tuple_impl(std::basic_ostream<Char, Traits>& os, const Tuple& t, std::index_sequence<Index...>) {
    using swallow = int[]; // guaranties left to right order
    (void)swallow { 0, (void(os << (Index == 0 ? "" : ", ") << std::get<Index>(t)), 0)... };
}
template<typename Char, typename Traits, typename... Args>
decltype(auto) operator<<(std::basic_ostream<Char, Traits>& os, const std::tuple<Args...>& t) {
    os << "{";
    print_tuple_impl(os, t, std::index_sequence_for<Args...>{});
    return os << "}";
}
template<typename T> ostream& operator<<(ostream& out, const vector<T>& vec) {
    for (auto&& i : vec) out << i << ' ';
    return out;
}
std::ostream& operator<<(std::ostream& dest, const int128& value) {
    // https://stackoverflow.com/a/25115163/23881100
    std::ostream::sentry s( dest );
    if ( s ) {
        uint128 tmp = value < 0 ? -value : value;
        char buffer[ 128 ];
        char* d = std::end( buffer );
        do {
            -- d;
            *d = "0123456789"[ tmp % 10 ];
            tmp /= 10;
        } while ( tmp != 0 );
        if ( value < 0 ) {
            -- d;
            *d = '-';
        }
        int len = std::end( buffer ) - d;
        if ( dest.rdbuf()->sputn( d, len ) != len ) {
            dest.setstate( std::ios_base::badbit );
        }
    }
    return dest;
}
template<typename T> void __read(T& x) { cin >> x; }
template<typename T, typename... U> void __read(T& x, U&... args) { cin >> x; __read(args...); }
#define read(type, ...) __AS_PROCEDURE(type __VA_ARGS__; __read(__VA_ARGS__);)
#define readvec(type, a, n) __AS_PROCEDURE(vector<type> a(n); for (auto& x : a) cin >> x;)
#define readvec1(type, a, n) __AS_PROCEDURE(vector<type> a((n) + 1); copy_n(ii<type>(cin), (n), a.begin() + 1);)
#define putvec(a) __AS_PROCEDURE(copy(a.begin(), a.end(), oi<__as_typeof(a)::value_type>(cout, " ")); cout << endl;)
#define putvec1(a) __AS_PROCEDURE(copy(a.begin() + 1, a.end(), oi<__as_typeof(a)::value_type>(cout, " ")); cout << endl;)
#define putvec_eol(a) __AS_PROCEDURE(copy(a.begin(), a.end(), oi<__as_typeof(a)::value_type>(cout, "\n"));)
#define putvec1_eol(a) __AS_PROCEDURE(copy(a.begin() + 1, a.end(), oi<__as_typeof(a)::value_type>(cout, "\n"));)
#define debug(x) __AS_PROCEDURE(cerr << #x" = " << (x) << endl;)
#define debugvec(a) __AS_PROCEDURE(cerr << #a" = "; for (auto&& x : a) cerr << x << ' '; cerr << endl;)
#define deb(...) debug(make_tuple(__VA_ARGS__))

/* pops */
#define poptop(q, ...) __AS_PROCEDURE(auto [__VA_ARGS__] = q.top(); q.pop();)
#define popback(q, ...) __AS_PROCEDURE(auto [__VA_ARGS__] = q.back(); q.pop_back();)
#define popfront(q, ...) __AS_PROCEDURE(auto [__VA_ARGS__] = q.front();q.pop_front();)

/* math */
template <typename return_t>
return_t qpow(ll b, ll p) {
    if (b == 0 and p != 0) return 0;
    if (p == 0) return 1;
    return_t half = qpow<return_t>(b, p / 2);
    if (p % 2 == 1) return half * half * b;
    else return half * half;
}

#define comb(n, k) ((n) < 0 or (k) < 0 or (n) < (k) ? 0 : fact[n] / fact[k] / fact[(n) - (k)])
#define fastcomb(n, k) ((n) < 0 or (k) < 0 or (n) < (k) ? 0 : fact[n] * factrev[k] * factrev[(n) - (k)])

constexpr inline int lg2(ll x) { return x == 0 ? -1 : sizeof(ll) * 8 - 1 - __builtin_clzll(x); }

void __exgcd(ll a, ll b, ll& x, ll& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  __exgcd(b, a % b, y, x);
  y -= a / b * x;
}

ll inverse(ll a, ll b) {
    ll x, y;
    __exgcd(a, b, x, y);
    return mod(x, b);
}

vector<tuple<int, int, ll>> decompose(ll x) {
    // return (factor, count, factor ** count)
    vector<tuple<int, int, ll>> res;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            int cnt = 0;
            ll pw = 1;
            while (x % i == 0) ++cnt, x /= i, pw *= i;
            res.emplace_back(i, cnt, pw);
        }
    }
    if (x != 1) {
        res.emplace_back(x, 1, x);
    }
    return res;
}

vector<pii> decompose_prime(int N) {
    // return (factor, count)
    vector<pii> result;
    for (int i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            int cnt = 0;
            while (N % i == 0) N /= i, ++cnt;
            result.emplace_back(i, cnt);
        }
    }
    if (N != 1) {
        result.emplace_back(N, 1);
    }
    return result;
}

/* string algorithms */
vector<int> calc_next(string t) {  // pi function of t
  int n = (int)t.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && t[i] != t[j]) j = pi[j - 1];
    if (t[i] == t[j]) j++;
    pi[i] = j;
  }
  return pi;
}
vector<int> calc_z(string t) {  // z function of t
    int m = t.length();
    vector<int> z;
    z.push_back(m);
    pair<int, int> prev = {1, -1};
    for (int i = 1; i < m; ++i) {
        if (z[i - prev.first] + i <= prev.second) {
            z.push_back(z[i - prev.first]);
        } else {
            int j = max(i, prev.second + 1);
            while (j < m && t[j] == t[j - i]) ++j;
            z.push_back(j - i);
            prev = {i, j - 1};
        }
    }
    return z;
}
vector<int> kmp(string s, string t) {  // find all t in s
  string cur = t + '#' + s;
  int sz1 = s.size(), sz2 = t.size();
  vector<int> v;
  vector<int> lps = calc_next(cur);
  for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
    if (lps[i] == sz2) v.push_back(i - 2 * sz2);
  }
  return v;
}
int period(string s) {  // find the length of shortest recurring period
    int n = s.length();
    auto z = calc_z(s);
    for (int i = 1; i <= n / 2; ++i) {
        if (n % i == 0 && z[i] == n - i) {
            return i;
        }
    }
    return n;
}

/* modular arithmetic */
template <ll mdl> struct MLL {
    ll val;
    MLL(ll v = 0) : val(mod(v, mdl)) {}
    MLL(const MLL<mdl>& other) : val(other.val) {}
    friend MLL operator+(const MLL& lhs, const MLL& rhs) { return mod(lhs.val + rhs.val, mdl); }
    friend MLL operator-(const MLL& lhs, const MLL& rhs) { return mod(lhs.val - rhs.val, mdl); }
    friend MLL operator*(const MLL& lhs, const MLL& rhs) { return mod(lhs.val * rhs.val, mdl); }
    friend MLL operator/(const MLL& lhs, const MLL& rhs) { return mod(lhs.val * mod(inverse(rhs.val, mdl), mdl), mdl); }
    friend MLL operator%(const MLL& lhs, const MLL& rhs) { return mod(lhs.val - (lhs / rhs).val, mdl); }
    friend bool operator==(const MLL& lhs, const MLL& rhs) { return lhs.val == rhs.val; }
    friend bool operator!=(const MLL& lhs, const MLL& rhs) { return lhs.val != rhs.val; }
    void operator+=(const MLL& rhs) { val = (*this + rhs).val; }
    void operator-=(const MLL& rhs) { val = (*this - rhs).val; }
    void operator*=(const MLL& rhs) { val = (*this * rhs).val; }
    void operator/=(const MLL& rhs) { val = (*this / rhs).val; }
    void operator%=(const MLL& rhs) { val = (*this % rhs).val; }
};

template <ll mdl>
ostream& operator<<(ostream& out, const MLL<mdl>& num) {
    return out << num.val;
}

template <ll mdl>
istream& operator>>(istream& in, MLL<mdl>& num) {
    return in >> num.val;
}

// miscancellous
template <typename T, typename U>
bool chmax(T& lhs, const U& rhs) {
    bool ret = lhs < rhs;
    if (ret) {
        lhs = rhs;
    }
    return ret;
}
template <typename T, typename U>
bool chmin(T& lhs, const U& rhs) {
    bool ret = lhs > rhs;
    if (ret) {
        lhs = rhs;
    }
    return ret;
}

#define functor(func) ([&](auto&&... val) \
noexcept(noexcept(func(std::forward<decltype(val)>(val)...))) -> decltype(auto) \
{return func(std::forward<decltype(val)>(val)...);})
#define expr(ret, ...) ([&] (__VA_ARGS__) { return (ret); })
template <typename Func, typename RandomIt> void sort_by_key(RandomIt first, RandomIt last, Func extractor) {
    std::sort(first, last, [&] (auto&& a, auto&& b) { return std::less<>()(extractor(a), extractor(b)); });
}
template <typename Func, typename RandomIt, typename Compare> void sort_by_key(RandomIt first, RandomIt last, Func extractor, Compare comp) {
    std::sort(first, last, [&] (auto&& a, auto&& b) { return comp(extractor(a), extractor(b)); });
}
template <typename T, typename U, typename Iterator_T, typename Iterator_U>
vector<pair<T, U>> zip(Iterator_T a_first, Iterator_T a_last, Iterator_U b_first, Iterator_U b_last) {
    vector<pair<T, U>> res;
    auto a_it = a_first;
    auto b_it = b_first;
    for (; not (a_it == a_last) and not (b_it == b_last); ++a_it, ++b_it) {
        res.emplace_back(*a_it, *b_it);
    }
    return res;
}
template <typename T, typename U, typename Iterator_T, typename Iterator_U>
vector<pair<T, U>> zip_n(Iterator_T a_first, Iterator_U b_first, size_t n) {
    vector<pair<T, U>> res;
    if (n > 0) {
        res.emplace_back(*a_first, *b_first);
        for (size_t i = 1; i != n; ++i) {
            res.emplace_back(*++a_first, *++b_first);
        }
    }
    return res;
}
template <typename T>
class ArithmeticIterator : bidirectional_iterator_tag {
public:
    using difference_type = ptrdiff_t;
    using value_type = T;
private:
    value_type value;
public:
    ArithmeticIterator(const T& value) : value(value) {}
    value_type operator*() const { return value; }
    ArithmeticIterator<T>& operator++() { ++value; return *this; }
    ArithmeticIterator<T>& operator--() { --value; return *this; }
    bool operator==(const ArithmeticIterator<T>& rhs) const { return value == rhs.value; }
};
template <typename T> vector<pair<int, T>> enumerate(const vector<T>& container) {
    return zip<int, T>(ArithmeticIterator<int>(0), ArithmeticIterator<int>(INT_MAX), container.begin(), container.end());
}
#define initarray(init, N) (__initarray<decay<decltype(init)>::type, (N)>(init))
namespace detail {
    template <typename T, std::size_t...Is>
    constexpr std::array<T, sizeof...(Is)>
    make_array(const T& value, std::index_sequence<Is...>) {
        return {{(static_cast<void>(Is), value)...}};
    }
}

template <typename T, std::size_t N>
constexpr std::array<T, N> __initarray(const T& value) {
    return detail::make_array(value, std::make_index_sequence<N>());
}
/*******************************************************/

// #define SINGLE_TEST_CASE
// #define DUMP_TEST_CASE 7219
// #define TOT_TEST_CASE 10000

void dump() {}

void dump_ignore() {}

void prep() {
}

int get() {
    read(char, p, q);
    p -= 48, q -= 48;
    return 50 * int(p) + q;
}

class quick_union {
private:
    vector<size_t> c, sz;
public:
    quick_union(size_t n) : c(n), sz(n) {
        iota(c.begin(), c.end(), 0);
        sz.assign(n, 1);
    }

    size_t query(size_t i) {
        if (c[i] != i) c[i] = query(c[i]);
        return c[i];
    }

    void merge(size_t i, size_t j) {
        if (connected(i, j)) return;
        sz[query(j)] += sz[query(i)];
        c[query(i)] = query(j);
    }
    bool connected(size_t i, size_t j) {
        return query(i) == query(j);
    }
    size_t query_size(size_t i) {
        return sz[query(i)];
    }
};

// __attribute__((target("popcnt")))
void solve() {
    read(int, n, l, q);
    vector t(l, vector<int>(n));
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j < n; ++j) {
            t[i][j] = get() - 1;
        }
    }

    vector<vector<pii>> ch(n);

    quick_union qu(n);
    auto work = [&] (int i) -> void {
        vector<bool> vis(n);
        auto dfs = [&] (auto dfs, int v, int u) -> void {
            if (vis[v]) return;
            if (not qu.connected(u, v)) {
                edgew(ch, u, v, i);
                qu.merge(v, u);
            }
            vis[v] = 1;
            dfs(dfs, t[i][v], v);
        };
        for (int v = 0; v < n; ++v) {
            dfs(dfs, v, v);
        }
    };

    vector e(n, vector<int>(n, INF));
    for (int i = 0; i < l; ++i) {
        vector<int> rev(n, -1);
        vector<int> ss;
        for (int j = 0; j < n; ++j) {
            if (rev[t[i][j]] != -1) {
                ss.emplace_back(rev[t[i][j]]);
                ss.emplace_back(j);
            }
            rev[t[i][j]] = j;
        }
        int dest = -1;
        for (int j = 0; j < n; ++j) {
            if (rev[j] == -1) {
                dest = j;
            }
        }
        if (dest != -1 and ss.size() == 2) {
            chmin(e[ss[0]][dest], i);
            chmin(e[ss[1]][dest], i);
        } else if (dest == -1) {
            work(i);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (e[i][j] != INF) {
                Edgew(ch, i, j, e[i][j]);
            }
        }
    }

    vector<vector<int>> bk(n);
    for (int i = 0; i < n; ++i) {
        bk[qu.query(i)].emplace_back(i);
    }

    vector dis(n, vector<int>(n, INF));
    for (int i = 0; i < n; ++i) {
        min_heap<pii> q;
        dis[i][i] = -1;
        q.emplace(-1, i);

        vector<bool> vis(n);
        while (q.size()) {
            poptop(q, d, v);
            continue_or(vis[v], 1);
            for (auto&& [u, w] : ch[v]) {
                if (chmin(dis[i][u], max(d, w))) {
                    dis[i][u] = max(d, w);
                    q.emplace(dis[i][u], u);
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        int s = get() - 1;
        int t = get() - 1;
        int k = get() - 1;
        cout << (dis[s][t] <= k);
    }
    cout << '\n';
}

int main() {
#if __cplusplus < 201402L or defined(_MSC_VER) and not defined(__clang__)
    assert(false && "incompatible compiler variant detected.");
#endif
    untie;
    prep();
#ifdef SINGLE_TEST_CASE
    solve();
#else
    read(int, t);
    for (int i = 0; i < t; ++i) {
#ifdef DUMP_TEST_CASE
        if (t != (TOT_TEST_CASE)) {
            solve();
        } else if (i + 1 == (DUMP_TEST_CASE)) {
            dump();
        } else {
            dump_ignore();
        }
#else
        solve();
#endif
    }
#endif
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

2
5 2 4
0305040201
0404040404
030300
020500
050102
020501
6 2 4
030603010601
010203060504
030202
060402
050602
060401

output:

1011
0100

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

1
3 3 6
020202
030301
030201
020102
030203
010201
010303
020303
010202

output:

010101

result:

ok single line: '010101'

Test #3:

score: 0
Accepted
time: 78ms
memory: 3656kb

input:

200
10 10 5000
01060:04020305080709
0103070:060204050908
09070503080401060:02
050308010204090:0607
03010502040607080:09
03080109020504060:07
06050:09040302080107
07080305010409060:02
030809010:0204060507
0:060908070201050304
060700
090:03
09080:
070405
010703
0:0100
080601
030600
070206
0:0:09
08040...

output:

011110001101101111111111111111111101111111110111011110110110111011010111111111111111111101111111111110111111110111111111111101111111111110111111111111111111110001100111111111111111111111111011101111111111111111111111111111111111111111011011110100111110111111110111111100111111101110111111111101111110...

result:

ok 200 lines

Test #4:

score: 0
Accepted
time: 183ms
memory: 35076kb

input:

1
2000 1 1000000
M=:]A@8UAY7W2JJ4KEHIA[HSCQ1ENSC`JXR;F3PJ:_@41P9Z=9HR8P<<:DUXRR9^WOQFL?NZP6S@=J0^WE32=6;\U0?88]Q_RNPUMT6YU<4<S]H?:7OCQYOT4YAV1^764ENWSDBED>M7A:BI>KSIR48JQ9B=N\5T3N4A2aF0@>3TI81<G7;YE>W`NMP<:IT4CI3D0=GZC3I\CLQJQBA9BDIS9SAM55KaVA<Z@D=>:Y?CQHUQ5U3a6UVI8OKX9_FAF^7=5M85;<0;8YPAM<7Z7PP7A=N...

output:

000101000101100010001000000010010110000001000001001100000000010000100001000000101100000000010000001000000001110000010110100000111100100000001000000000011001010001000001001000100000000100011001100110010000010000101100000011111000000010000101010010000000010101000001010111100000100000000000000101000100...

result:

ok single line: '000101000101100010001000000010...0101000101000000000010101001000'

Test #5:

score: 0
Accepted
time: 356ms
memory: 51048kb

input:

1
2000 2000 1000000
FVAaH7GRPO;_11Da5J18@3SMG==\G8E8S^6:M4L0JH>MN5IXT>2<7WJ3U8LVJS=;;3F13>0D0>VOIIU@EPHG6ABL6;K?T1PXDERLG07]5C9^GDKG<SBMIW;`4W8P3=469TIPKH0O34523_J5C2MJ17D25Z@=K8H@M>WK<CMK7EO]BPD7B6AW741J5YIHIa1:ERSG>L3N2^F3<4F`DLE@2AA5=8GZK6:192FB736[WMV7:^DA2C:<LK040VJBM3M]WXU50`407TR_?PLF@5VL7OSL...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #6:

score: 0
Accepted
time: 511ms
memory: 50916kb

input:

1
2000 2000 1000000
0102030405060708090:0;0<0=0>0?0@0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z0[0\0]0^0_0`0a101112131415161718191:1;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a202122232425262728292:2;2<2=2>2?2@2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000...

result:

ok single line: '000000000000000000000000000000...0000000000000000000000000000000'

Test #7:

score: 0
Accepted
time: 538ms
memory: 50996kb

input:

1
2000 2000 1000000
0102030405060708090:0;0<0=0>0?0@0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z0[0\0]0^0_0`0a101112131415161718191:1;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a202122232425262728292:2;2<2=2>2?2@2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X...

output:

010001100010000000101000000110010001001010101100100100000001000000101010100010000001011111010000000001001000010101011111001010101010100100010001011011000010010100110110000100010110101110000011111101100110010100100101010000100100101110100000000101100010100111000011001110100010001010000101111001101000...

result:

ok single line: '010001100010000000101000000110...1010101000010010101000100000111'

Test #8:

score: 0
Accepted
time: 264ms
memory: 50664kb

input:

1
2000 2000 1000000
0102030405060708090:0;0<0=0>0?0@0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z0[0\0]0^0_0`0a101112131415161718191:1;1<1=1>1?1@1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1[1\1]1^1_1`1a202122232425262728292:2;2<2=2>2?2@2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X...

output:

011010100000000000000000001000001100000110000000100001010000000000000010001000000100000000000000000000100000100000000001100000100011010000000000000000000000000010000001000000010001100010000100000001000000000010000000000000001000010100000000001000000000000000000000001100010000000000000101000000101010...

result:

ok single line: '011010100000000000000000001000...0000000000000100000010010000100'

Test #9:

score: 0
Accepted
time: 350ms
memory: 50896kb

input:

1
2000 2000 1000000
1REKN]@]>9D9177?6E8DU65LCS>X3Z4KJ47@?R43H8C2ADQ<T[GGCZI]CO4SCDNAVCE534S1;0LV<:F[R`A[=89FL^BYGU7F:NBDD2F3SYLQS[O407E\V>>;EOTL=W8VAYMRO[KHRZ7^F6?:<G4R9O3AVG1\1OER1MKNMG01R?=;SWMP28:X>2=GLC1LSU<VMKQ5?KQAS^4QDTC07TK=R01WL@6596@D5IKT?YG?HaQPP:<12ZUF?GARFKJXC`NFIaJ;SXC:80V1Q@Q;FJV]3XSJ...

output:

111101100101100100000000101000110011010001100000001001101000001000010101010010100111100010100110000001000000011101001010110000101000111000010011110100010101100101011111000010000001100001000011010001101000000010100011000110101001100010111010110011001101110010001110110101000000110111010100001000011001...

result:

ok single line: '111101100101100100000000101000...1100010101000011110011110111100'

Test #10:

score: 0
Accepted
time: 65ms
memory: 3824kb

input:

1
1 2000 1000000
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
0...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #11:

score: 0
Accepted
time: 335ms
memory: 50996kb

input:

1
2000 2000 1000000
1ILZ2@SO4;BPWLFN@6HMAVQ]NNKR2NU30EP@3WF73^1BSKIP:VS7KQA>T\T63TAAK]8a4@7F0LD3V4LRN?M105L@>A<5D@S=MI9G9O<7<UQaF61VK;EQBEG`F8DOJ?L67;CL=@Q_IAPU2TP:43=O42I85UC\2L18KKP5MSFX73;\PFCQ:IB9?M<:FI?;N1I1>362O:;:1WQ6=Q7T=RW\WJMTQJ40U6JU>_@H:H6K0Y?[>H@K6@5AG]OEUEH>3G5C@OJ1E8O0CaO68??>A\C`:F8T...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #12:

score: 0
Accepted
time: 320ms
memory: 50740kb

input:

1
2000 2000 1000000
=H=4F4S`A?@V<E8]HBU>190VP7EDDC6EH3P4CP6K2Z3OP@LI<7H`OM:F:=FOH9BW=<1ZGIK^7P0<9RK73Z1EFKO5QC5L25TCV`HT3D@RQ_2GE<SK;_D^0;>FSL5X9_Q0L\L7TW@_ULQE0Z;MG1O:3>F<MX=:V];@=1A@;^V^E\;F:[8S@SFY340R=@Wa8NSMS[UC5KV6JNV3EA<80_;a>`2:>A28OI=EL2?aTDL3WRNY4H8R2aIY14DAHJ>6UIEOS_?=AF6];\BK3]?<TYU5=`3^...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #13:

score: 0
Accepted
time: 72ms
memory: 3708kb

input:

200
10 10 5000
08060705040203010:09
0201090:080706050304
0201050903080:060407
0305010:020706090804
030901080:0706040205
0509070:010803060204
0:060709080203050401
0309010806050:040207
020106090703050:0408
0603020908010:050407
020700
080907
020305
070407
050509
080502
010100
020206
050809
0:0807
02040...

output:

011111111111111111101111111111111111111111111111101011111011111110111010111111111111110111111111111111111011101111111111111010110011011111111111111111011001110110101111110100111101111101101111011111111111111111111110011111110011111110111111101111111110111100111111111111111111111111111111111101011111...

result:

ok 200 lines

Test #14:

score: 0
Accepted
time: 70ms
memory: 3652kb

input:

400
5 5 2500
0405020501
0404050302
0105050105
0304010205
0402030205
040200
010203
040203
030503
050201
010502
010505
030304
020504
050503
050105
030101
020403
030403
030200
010500
050500
030403
050101
040205
030501
010503
050400
030505
040303
050101
020101
050502
020104
050101
040503
010205
050404
0...

output:

000000010100000010010000100110000010010000100000100110011000100110101000010000010010010111000000011000001000000010000011010000000110000110010100101011010010110100011000000010011010110000100110111000000101001010010100010000111101011010111101001100000011100001000000000000111000000001100010001100010000...

result:

ok 400 lines

Test #15:

score: 0
Accepted
time: 86ms
memory: 3820kb

input:

20
100 100 50000
1C0=0Z1Y1A1V0U1]0M0\1:0H0a0F1J141B120T06031S1F05151H0`1Q0]0^0R0A1W0E0J1X1a0G0?1@1=0S1<0O1_0X04011N1D090D0:0L0V1^0Q0[190B071G0P0217081M0N0Y1I0@1T1O1E1[0>0I1\1>1U1L1?200_131K0Z0W181;1R0K0<1P0C1011161`0;
1K0E0@1a0Y0K1V1\0403121L0a0R0D1H1Z0[0Z0S200<1I1A0W1B0?1N1W1C0P0N0Q150C080`100_0516...

output:

001101110111011111111101110111111111110111111111111111011111111111111111111111111011111111111111110111011111111111111111110111111111011111111111110111111111111111111111111111111111111111111111011011111111101011111111111111111111011110111110111111111111011111111111101101111101111111111111111111111111...

result:

ok 20 lines

Test #16:

score: 0
Accepted
time: 653ms
memory: 51260kb

input:

1
2000 2000 1000000
W^P_@WECKD6O6H9X@FS00U721QG\HE7GB4@`VV9Z52AC3OWC?MU[:2K1C?J\AFMA;OHXC_4B:PUa>:8[3\O^G4P2UAIaTEH4JCW<;CMC4CKMQL=335<42`EZ1^Ja?F2NN`=BE87959S?PCD7T]HNUKMXDR28T75OAIQ0G7>Y:<CDA\<<S`8I92T>EXBWO<40B9RE9NG>:[@LLE;Y253J1N9B>5<X@3RQ;<8W42;5CE11<M14>JBUL:@BJA5WR\RJ09QA;:F]QC8H@\3WM]:>>WPF...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #17:

score: 0
Accepted
time: 70ms
memory: 4092kb

input:

1
20 2000 1000000
020;0C070804090@080B050:0?0A0>01060D0=0<
0>0=010<060;05070D03080:020=04090@0A0?0C
090206010B0;050@030C0D0<0=040?080A070?0:
060A0?0D070502090=0B030;04080C0@0:0B0<0>
0B0@0A070?0:0209080;0=040<060>0203050D0C
0C09040B02030>0?0@0<070=01080=060D050:0;
030=0?080A0A0B060:0D040>02010@050907...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111101...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #18:

score: 0
Accepted
time: 71ms
memory: 4056kb

input:

1
40 2000 1000000
0R0G06040F0:080D0S0P050U0E0?0A0>0A070C0K0O0@0N0M0X0V0;090J0B0L0H010=0T0I030Q0W02
0K0E0I080M0Q0L0>0T0V0?0P070=0D020:0R0@0>09060X050G040O0U0J0H0S0<010F0W0N0A0B030C
0>0K0G0<0F0J0=0E0C0?0P030H0X0@0;0I0U0O0:0T0Q080S0A0N060D020H070M0B0V090L0504010W
0X0M0A050H0C0V070<0K0K0E0I0B0@0N0R040?0...

output:

111111111111111111111111111111111111111111111111111011111111111111101111111110111111111110111111111111111111111111111101111111111111111111111111111101111111111111111111111101111111111111111111101111111110111111111111111111110111111111111111111011111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111011111110111'

Test #19:

score: 0
Accepted
time: 98ms
memory: 6636kb

input:

1
300 2000 1000000
5H2;4H4G2I5E4Y115a0;4C3W4^424S4?401S105`5<5[0N3U3M3<1F1C332a1a0H4a5Y061O5K352P5^0B5A1X4F4B140>3J28412<383?0P300I2K5J5B2Q4\3T2T4X2U4U0@3Y3^0G600O3X5P3Q1N0?375M080D3I5=5F1R562G2@392^4_2:073>0a3L513E5S4:24482E0V4`4Z3O3F2S3D5:2Y594@4J135L0M1=1Z4W1W1B2?0J4N0A1?5I3C3B0529541E1;0Y0W532_2...

output:

101110011011111001110111111110101111111011111111111001111111111111001101111111111111110111111111111111111100111110111111001111111111111111111111111111110111111111011110111111111111111111101011101111111101111111111111111111111011000111011011111111111111101101111111010101101111011111111011111110111011...

result:

ok single line: '101110011011111001110111111110...1001111111111011111111110100111'

Test #20:

score: 0
Accepted
time: 671ms
memory: 51168kb

input:

1
2000 2000 1000000
3OIPR;WRK8GM503<Q@9>98J;W01U;>@Q<D9=BY4_A9AW@Z0ND;02C^X0RV<JS5W@7VW4L2Aa<MIM8I1\T6AX=OR0J]4XS>8[JJ?R0DK=J1D7H4SRMP7N;F7`;\K;@V2>4]F09W5UN9CD7>41OJOH:W<>GAI6:^NOTUB^83HXK1CZ:2O`W;P>F[F?EFIY?WSMM5N\FZG;DC0GLOP5<=5VWW0E=?7KT29D3S6EIJ7PDAD[POKTS81]G85`=6FAFVW9D34SKBHJ51C:>Q6a@_?NCB4Z...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #21:

score: 0
Accepted
time: 217ms
memory: 50700kb

input:

1
2000 1998 1000000
V1NAFXH:;6W9?ER19O55J_C7LFCC5=P;487_5:<V=MC688PPUTWBNT97;YE71V@85Q@7CVAZ6MKQKRW@K74MLS29V]MH3I@YM1<N@D9\D;PM<`7>UI6R45EEO]VSO2PJAI4FIJ5RAL0XD:=1E?UC@;1>MR2D;LFL1GH[9G:@J=><U3<BD\J>4`ONSWTASB7;60L0EQNQ@^IMG`1Q2R7<I=U>IYDL:LTK3_B_1C:9E:6FJIABK4V=D@<JOM9?S1JG7KN90?>AU^2N8PJ89JL25GFQ...

output:

111110111111111111111111111011101101111111011111101111101111111111111110111101111111101111110101111111111111101101111111111111111011101111111111111111111111011110111111010111111011111111111101100111011111111111100101111111111111111111111111111111111110011010111111011011111110111111110111011111111111...

result:

ok single line: '111110111111111111111111111011...1111111111111111111111101111111'

Test #22:

score: 0
Accepted
time: 390ms
memory: 48540kb

input:

1
2000 1748 1000000
1>H40MN6F;2RQ`T1G<H3IVV^GAO:>>M\JXL`1Z97:CC]<;P44FRR8Z8Y=R4;@[WO?3:^9DCC8P0NCYBLJ14O?^M=3@D42^G150M9?\N_P94W?AKYK2VI>II^MT3>?a9STR3Y5O?M7[<V;PE232TTJ5@:N:T^KT7DL;4RSNG>=<W]G^A>5`L:1;:2?VNP?:=W<[9\;TNARGQXL_2UFWIKR_?I2D4\KO;\BIB4CVW5DF;=US1HEBIS2EG?7aMN@9CQW4RSC871NNA=5MM`WK?[B:HX...

output:

010000010000000000010000001001110000000001000000010000000100000000100101000000101100001010010110001000100010000000001101110000000010100011001001000010111000000001011100011101000100000000010000000001011010100100010011000000100110010100100100101110111001010101110101000101001011000000000001100111100000...

result:

ok single line: '010000010000000000010000001001...0001010101011110100001000001100'

Test #23:

score: 0
Accepted
time: 378ms
memory: 48620kb

input:

1
2000 1748 1000000
O\;@;JV0<48GC4;_@`KP3V5W0M>;CEWU=;5DX0@6>GUYH0F887EM@I5JU\PSE^I\G\WaK_FWLGTNO[PLRBLAVJO;BZBE24:AWZE:4L54;BJ21E<N5`G?G7>K5a1KHMF`==HVNXO>9L7QAST;LP7X1:L>J^QDRP:WJ<V7?8D0AF@93P:6;]OFM=G=;K;VRGCYKQBJ:XJ@4VW\JEHGC7UMNMJ]N[K9<C>CQ74@LJ2FQ81961VM;66I2G<99=F7KN2\BXBK4QG4UN9;QaND9>3MU2P3...

output:

010000000000000000000001010001110001000100101101010100101000000000011011101100111010100001011100000000000000101000101000100110001010110001000010111000001000011100100000101001010000010000001001000010001000100010100100000000110010110000000000001010100001101000100010100001001000000000001100100000010000...

result:

ok single line: '010000000000000000000001010001...0100111000000000000100110000011'

Test #24:

score: 0
Accepted
time: 286ms
memory: 50708kb

input:

1
2000 2000 1000000
5S6QR;UOQMV=N`CJ038EOY3UEHU?5?=F3G?VBSW9BVVZENCD2NGPGFO@BYTR4==3S0O=K?O:DVP\3VT_G2U3167JLLMJ1^3\E><_>6F?EXLJM30V:;RR:=<M43U=KUDa?[?KHHS`Aa?NEI5ZTSMZNITX:WKK?R;4;8DKI0B3U1G>KS3;P6WUWK4FFE1UK@D?88MLR@L^6YWZNQ94VF4BLZR?GRGHUJQ00QAWTU12@Q9O5IO7JSB[6@?5IW<S5LIHMUM\EJWH0=RS;9GOEW5=Ka=K...

output:

111100111011011000110101111111010100001101110010111111110011111110011011111111111101111001010111111110111100111111101111100110011000100110011111111111011111011110111110111111101111100110011101111110011101111011101010111111100111111011111111100010011111111010011100101111111011110101010111111100101111...

result:

ok single line: '111100111011011000110101111111...1111010110110111101111011001110'

Test #25:

score: 0
Accepted
time: 151ms
memory: 35228kb

input:

1
2000 2 1000000
4;9AA8?CSQ@NS@5K7Q7UEK=I<O1DU]7BA>I;OT82JG;MK\3DD6QVHSH`3M9SAONPKNEIK:R?MMGK6YQHTGW<7YP>4NMTU2@YW=G:L786JHHQ=T38P96PJXTC@aGM@>?KB2O[:X>SUDOYPS:Y4S1:;E15SNVK>XB\UGB8:U@WCDD^<6N2;]G8=\F[7AKLI<76AUN0?X920aKGIR7IF9L3T51;DX8?7]6J?VT\<U1M@C=CBZO2D59T>NNISZ5;7KOH:^@JKUM4C463NFR<=SCS4D;`J[C...

output:

101100100001110111010101111110111011111111101011111101111101110111101111101010101101111100101111101111111101011010111111111111110101010111111101111111111111110101100001001110111110111111110111011111111111101110010111111110111110101101100011011111111010110111111111101110111111011111011011111111000101...

result:

ok single line: '101100100001110111010101111110...0111111101010101111100110111111'

Test #26:

score: 0
Accepted
time: 316ms
memory: 50788kb

input:

1
2000 2000 1000000
E>?>RH09F?DF@`>I;^>DE[@DL2JVM`DU566CQVWR?YC3R^O_C?IFGIQ^JN?:V7CYKL2I3YJAJXKSCN4TC6Q44^1ADNH89F>6FM9[4@8:Q?VPKX=^@C?7S^;@QSN>M26a1?4S2C?T;U422\V?1G>E7F1JE\4D;:>0LUA6B<V_1NNS4WF;KW6`@aR19HRaQYI_2H02UE;Y<^DBODW?UT8DT^7>NIDXLFWK<99:P[9G3K>V>S2BSSHBAI<;SA@1==W=5OC[R=1LRB7?AD;5MY<MAXDL...

output:

110010111010101000001111011101001100101000100001001000100010000010110010010101010110000001010101001010101011011010001010110010101110111010110110001010101001100000101100110001001101110010001110111010001111101011110000001010100011110001110111100010110111001011000111100111110011000111011011010000111111...

result:

ok single line: '110010111010101000001111011101...0110011011100110001101001011110'

Test #27:

score: 0
Accepted
time: 336ms
memory: 50656kb

input:

1
2000 2000 1000000
@<N24\4KM58;0M5@JR7OO`QX6aC^A366R^=NG4?\HHA8H:IV4=:YW@HT=H81U;MB=8Q^QUC36<=]G0@C:UEDM1GP>3:221<GSPRG@a8V?WFWQ7BP7ZINAQSO?P?Q?N@1J;W307F=<TTV807;B0P`KG9Q5ZJNRA@SFN4Z<DQ\7a6_3UCRU_R;W7?MVOSH7R3O=VKYQ=@Z9A1M4?2CRE882<DOJ?EO=\G`WKO;WIOG<Y60D@O9KU5aT9EG>YH0KJX027:ZEISaF32RW<8K?YPCBEWR...

output:

111010100001001010000011100001000010010101100111010100000110001000100000001000010011000000111001100011001010101001000100011000000000100110010110001011001110000000010010100001101011100011110000001010000000111111100010110010001110010001001000100010001000000010000100100000101010011000000110010011101010...

result:

ok single line: '111010100001001010000011100001...0000100100100001000110001100001'

Test #28:

score: 0
Accepted
time: 254ms
memory: 50788kb

input:

1
2000 2000 1000000
?MP98`76051@ANJ?HLOMD@4M0=?;18=VJB7[7MFR22S1W2@4;VNLM7JRCA=U23A=4VAD@ED09OHPR5Ta0YI?R]0\U10`SVJ9SJA:OHUO9U140WL4A3LQ2L9F9G3`6IU<H13F1AQ4P^WT11;8:5K8R?VKW]ULOJ3SR^M?<E=8H2=AP3FQHB1KRFJW;C6G7^Ca@LRY6UK<3DVARSO7AX8HU2L\B@VI:YP@I6TBMXK?5J1V972<Q]GDD[IOQ:HHHWJ[8B8@<45XJM4XS?2YK]K5H=QN...

output:

000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000...

result:

ok single line: '000000000000000000000000000000...0000000000010000000000000000000'

Test #29:

score: 0
Accepted
time: 89ms
memory: 4112kb

input:

10
200 200 100000
170M2B1`0R330J2`3^0\2@263C0T3W2M2Z2T3;1>200>2W3Y2J1_3\250A2:2?241O2Q3E1F16020L3V2I0G1:0U373`350_110Z1I381L2Y3N3>3@123:361Z3O1a2834132_0:142G2]1H0S2^3K1W1K2F0;1D1G052304012C2N213L323S29401B0=1A3J1R1=3_1V3Q3I0]2X3X2L2;0B2<1P3H2A0W180V3R0P092S081X073B0X300C192=3<3?0K0<2O0F1Y1?2K032H3P...

output:

010110010011110100101101111101011101010101111011000111101101111011111000000000100010111011101101100110110111111110110001101111010001001111111010110100111110110111111111111000110101111001111001100011111011110101110110110110001110001010011101111100101110001111111011011101100011111110111001111001101011...

result:

ok 10 lines

Test #30:

score: 0
Accepted
time: 73ms
memory: 3740kb

input:

20
100 100 50000
0N1X190_0\1B0G0=1^1Z151N0U160?1=0502041U1;0O0[0I0Z0S1K1P1T090>0`170J1L121I0M1_0;1J1W0A1`0]0T1Y0R0:1a110Q0H1M1V1E0D0F101:0@1<13180B1>1]030L1?1[060X200E0Y0W1G1C0C1Q0K0P1S1R0V081D1@0a011H0^0<1F1A1\1O1407
1_0A1C090?101Q17061?1Z19160@0R131O071\1<0O1U0:1@0T0a1403051]0I0V0Y0`0[0>1E02041D1J...

output:

011100111101000111011100011101111111101111001110111100110010101110110111101111111100001001010010100111100100111001000101110101000110110111011011000111010111111110101110000011111011001101111100000110111111000000110001100000101100101000100000111011011101011001111110001111011010010110000010001011111011...

result:

ok 20 lines

Test #31:

score: 0
Accepted
time: 65ms
memory: 3820kb

input:

1
1 2000 1000000
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
01
0...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Extra Test:

score: 0
Extra Test Passed