QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#595457 | #9431. The Quest for El Dorado | ucup-team112# | AC ✓ | 364ms | 145780kb | C++20 | 13.9kb | 2024-09-28 13:45:31 | 2024-09-28 13:45:31 |
Judging History
answer
//#define _GLIBCXX_DEBUG
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif
#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a) (a).begin(),(a).end()
#define ALLR(a) (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
namespace template_tute{
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max<ll>({a,b,c})-min<ll>({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}
template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};
template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
auto tmp = v;
for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
}
template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
rearrange(ord, head);
rearrange(ord, tail...);
}
template<typename T> vector<int> ascend(const vector<T>&v){
vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
return ord;
}
template<typename T> vector<int> descend(const vector<T>&v){
vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
return ord;
}
template<typename T> vector<T> inv_perm(const vector<T>&ord){
vector<T>inv(ord.size());
for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
return inv;
}
ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
ll modulo(ll n,ll d){return (n%d+d)%d;};
template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int popcount(ll x){return __builtin_popcountll(x);};
int poplow(ll x){return __builtin_ctzll(x);};
int pophigh(ll x){return 63 - __builtin_clzll(x);};
template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t 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;
}
namespace converter{
int dict[500];
const string lower="abcdefghijklmnopqrstuvwxyz";
const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string digit="0123456789";
const string digit1="123456789";
void regi_str(const string &t){
for(int i=0;i<t.size();i++){
dict[t[i]]=i;
}
}
void regi_int(const string &t){
for(int i=0;i<t.size();i++){
dict[i]=t[i];
}
}
vector<int>to_int(const string &s,const string &t){
regi_str(t);
vector<int>ret(s.size());
for(int i=0;i<s.size();i++){
ret[i]=dict[s[i]];
}
return ret;
}
vector<int>to_int(const string &s){
auto t=s;
sort(t.begin(),t.end());
t.erase(unique(t.begin(),t.end()),t.end());
return to_int(s,t);
}
vector<vector<int>>to_int(const vector<string>&s,const string &t){
regi_str(t);
vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
for(int i=0;i<s.size();i++){
for(int j=0;j<s[0].size();j++){
ret[i][j]=dict[s[i][j]];
}
}
return ret;
}
vector<vector<int>>to_int(const vector<string>&s){
string t;
for(int i=0;i<s.size();i++){
t+=s[i];
}
sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
return to_int(s,t);
}
string to_str(const vector<int>&s,const string &t){
regi_int(t);
string ret;
for(auto z:s)ret+=dict[z];
return ret;
}
vector<string> to_str(const vector<vector<int>>&s,const string &t){
regi_int(t);
vector<string>ret(s.size());
for(int i=0;i<s.size();i++){
for(auto z:s[i])ret[i]+=dict[z];
}
return ret;
}
}
template< typename T = int >
struct edge {
int to;
T cost;
int id;
edge():to(-1),id(-1){};
edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
operator int() const { return to; }
};
template<typename T>
using Graph = vector<vector<edge<T>>>;
template<typename T>
Graph<T>revgraph(const Graph<T> &g){
Graph<T>ret(g.size());
for(int i=0;i<g.size();i++){
for(auto e:g[i]){
int to = e.to;
e.to = i;
ret[to].push_back(e);
}
}
return ret;
}
template<typename T>
Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
Graph<T> ret(n);
for(int es = 0; es < m; es++){
int u,v;
T w=1;
cin>>u>>v;u-=indexed,v-=indexed;
if(weighted)cin>>w;
ret[u].emplace_back(v,w,es);
if(!directed)ret[v].emplace_back(u,w,es);
}
return ret;
}
template<typename T>
Graph<T> readParent(int n,int indexed=1,bool directed=true){
Graph<T>ret(n);
for(int i=1;i<n;i++){
int p;cin>>p;
p-=indexed;
ret[p].emplace_back(i);
if(!directed)ret[i].emplace_back(p);
}
return ret;
}
}
using namespace template_tute;
template< typename Monoid ,typename F>
struct SegmentTree {
int sz, n;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1), n(n){
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
if(a>=b)return M1;
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
//[a,x]が条件を満たす最初のx,満たさなければn
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return n;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[a]);
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return n;
}
//[x,b)が条件を満たす最後のx,満たさなければ-1
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
void print(){
for(ll i=0;i<n;i++)if((*this)[i]==M1)cout<<"x ";else cout<<(*this)[i]<<" ";
cout<<endl;
}
};
namespace range_max{
using M=ll;
auto f=[](M x,M y){
return max(x,y);
};
SegmentTree<M,decltype(f)>make(int n){
return {n,f,-INF};
}
}
void solve(){
ll res=0,buf=0;
bool judge = true;
ll n,m,k;cin>>n>>m>>k;
Graph<ll>g(n);
rep(i,0,m){
ll u,v,c,l;cin>>u>>v>>c>>l;u--;v--;c--;
g[u].EB(v,l,c);
g[v].EB(u,l,c);
}
vector<vector<ll>>idx(m);
vector<ll>a(k),b(k);
using S=decltype(range_max::make(0));
vector<S>seg;
rep(i,0,k){
cin>>a[i]>>b[i];a[i]--;
idx[a[i]].PB(i);
}
//OUT("Aaa");
vector<P>dp(n,MP(m,INF));
rep(i,0,m){
ll sz=idx[i].size()+1;
seg.PB(range_max::make(sz));
rep(j,0,idx[i].size())seg[i].set(j,b[idx[i][j]]);
seg[i].build();
//seg[i].print();
}
dp[0]=MP(0,0);
QP<pair<P,ll>>q;
q.push(MP(MP(0,0),0));
while(!q.empty()){
auto [p,now]=q.top();q.pop();
//OUT(p,now);
//OUT(dp);
if(dp[now]<p)continue;
for(auto e:g[now]){
ll to=e.to,len=e.cost,label=e.id;
P nxt=p;
if(a[p.fi]==label&&b[p.fi]>=p.se+len){
nxt.se+=len;
}
else{
int npos=lower_bound(ALL(idx[label]),p.fi+1)-idx[label].begin();
int nidx=seg[label].find_first(npos,[&](ll x){return x>=len;});
if(nidx>=idx[label].size()){
continue;
}
nxt.fi=idx[label][nidx];
nxt.se=len;
}
if(chmin(dp[to],nxt)){
q.push(MP(nxt,to));
}
}
}
string ret;
rep(i,0,n){
ret+=(dp[i].fi<m)+'0';
}
cout<<ret<<endl;
}
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
ll res=0,buf=0;
bool judge = true;
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
2 5 6 4 1 2 1 30 2 3 1 50 2 5 5 50 3 4 6 10 2 4 5 30 2 5 1 40 1 70 6 100 5 40 1 30 3 1 1 2 3 1 10 1 100
output:
11011 100
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 109ms
memory: 8032kb
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...
output:
1000110011110111110010100001010100100101000000 1100010010111011011011000000011000001100001000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1000000000000000000000101000010000001001000001 1001100010110000100001100000000011001110110 101010000000000000010...
result:
ok 1110 lines
Test #3:
score: 0
Accepted
time: 127ms
memory: 8544kb
input:
1110 41 95 66 37 16 1 93 8 38 13 61 41 25 7 10 40 26 13 90 18 34 12 84 29 21 7 22 32 41 10 52 20 17 18 273 41 31 2 163 17 11 20 316 24 14 7 35 1 5 7 39 26 38 13 48 10 15 14 154 4 7 12 8 13 6 20 139 18 9 10 90 16 33 7 54 9 35 5 39 36 31 17 9 10 20 17 74 37 34 13 6 7 9 9 153 12 7 18 173 5 7 3 194 21 3...
output:
11111010101111111011111111101111111111011 11111111111111111111111111111111111111101 11111111111111111111111111111111111111111 11011110111111111111111111111011111111111 10100010011110000001010100010110010000001 111111111111111111111111111111111111111111 100000000000100000000000000100100000000000 1000...
result:
ok 1110 lines
Test #4:
score: 0
Accepted
time: 298ms
memory: 99096kb
input:
1 200000 500000 179 94800 107033 1 16 64316 117022 8 184 105481 172922 2 53 37627 148708 9 37 179021 41825 10 29 177650 69319 5 20 144968 160008 6 68 54796 172626 2 201 35718 99731 3 127 45553 132280 2 433 199580 18097 1 116 77143 7273 7 90 49300 94594 8 231 52637 197546 8 62 156375 4265 2 54 136509...
output:
111111111011001111111110110111111100000111111111111011101111011111110011111111011111111101100111111111110100111111101111111111111111111111111111111111111111111101111111111111111101111101010111111111111111110111111110111110111011010001110111111111111101111110011111111111111111110110111101011111111111...
result:
ok single line: '111111111011001111111110110111...1110101101101111110110011110111'
Test #5:
score: 0
Accepted
time: 337ms
memory: 99664kb
input:
1 200000 500000 28600 134923 17846 1145 19 38550 190638 1881 173 153445 161902 1019 61 134582 132451 1259 32 27836 81432 1053 99 45363 165206 1879 453 173218 82373 1834 392 36060 180829 1434 93 158792 24019 1305 80 114091 131741 400 36 86750 83631 674 284 102965 26889 903 96 72980 92116 852 293 7814...
output:
100101111101011111011110111110111110111001110111001100100011001111111011111101111011111010111010010010011101100111101010111010011101011111110111111101110110110111111111000110110101011110111011110111011011001111111101111110011111010111110100111111001111010110110111101111111011111101001011101110111010...
result:
ok single line: '100101111101011111011110111110...0111111111111110001011011001011'
Test #6:
score: 0
Accepted
time: 229ms
memory: 108452kb
input:
1 500000 500000 132 33565 62505 9 27 159690 223311 5 72 136509 402294 1 30 335433 250256 8 32 46344 199283 1 53 101509 318328 1 91 154342 472216 1 98 219655 19442 6 8 488718 58652 1 64 88757 14212 1 51 92129 332927 10 69 418031 387995 5 1 433240 214628 1 67 402161 87957 2 84 107282 385626 3 86 18834...
output:
100100000001001001011000000000010101010000100000000011010010000010000001000000100010000000101010100000011010001000011111000000101001000010010100101010110100010011000000000010000000111010101010011001011100000011000010100000001000010000001000010000001100010100000000001000010001000000001100110000010110...
result:
ok single line: '100100000001001001011000000000...0100010000000010000000000001101'
Test #7:
score: 0
Accepted
time: 307ms
memory: 110836kb
input:
1 500000 500000 34800 356922 276405 1274 6 70376 56771 944 85 311347 288381 114 23 323396 269923 1542 25 403829 492566 1731 41 415774 97020 149 48 317081 340484 627 3 277226 227941 1804 69 349022 434891 1274 53 436085 437523 1274 83 110761 403042 1180 86 333338 341167 1274 88 4802 451135 1149 18 116...
output:
111001100110001100011110001011001010001111100000011100001101000011100110010111011011101111101110010101011111110000111101100111101010111111100110001011111111101111100010101001110001110100100111010011110111001100011000111011111111111110010100111001111010011000111001111111111100111010001110011011111010...
result:
ok single line: '111001100110001100011110001011...1101000100101011111011001110110'
Test #8:
score: 0
Accepted
time: 350ms
memory: 118244kb
input:
1 200000 500000 500000 138435 172074 2 320 40030 9389 6 35 61974 124326 6 64 4679 144065 8 238 47254 185524 1 74 138009 134825 8 235 164764 59275 5 227 134478 183172 7 69 131920 51571 3 140 119971 193848 6 98 130747 49642 9 376 67838 127653 1 30 32972 140348 4 1 39560 183382 10 15 151497 1703 4 274 ...
output:
101110010011111111000011100110111110111010011101100110001100101111001011100011100110011111001111111111100111111010000001011101011101111110111111110011110110111110000100101100111100101101001111111011001101110101101111100101101111110111100111110101001001010111100101101111100110110101001111101110110101...
result:
ok single line: '101110010011111111000011100110...1100010011101011101011101001011'
Test #9:
score: 0
Accepted
time: 341ms
memory: 121024kb
input:
1 200000 500000 500000 123878 17891 843 20144 35773 147691 427 7936 96800 135322 1787 8414 66660 124569 1948 30 103754 33455 1573 91 188810 189553 1180 89 106226 145102 1009 2028 77946 90544 33 7357 20000 127787 1284 6528 43787 82216 282 10 185497 15937 1211 12376 183320 77384 113 65 78356 71033 144...
output:
110101010101010111110011101111011001010000011001000100100000101100111101010000111101110110111010011011101110111010100110001110110110011011110101100100011100010110010010111000111011010100101011010100111000111010111010001001001001010110000000100111100010011110111100010011011100000011000101010100111001...
result:
ok single line: '110101010101010111110011101111...1011001110011011100011001010010'
Test #10:
score: 0
Accepted
time: 259ms
memory: 128520kb
input:
1 500000 500000 500000 426522 37213 5 70 324338 118732 7 21 455456 31351 1 25 269683 186562 3 92 297357 444426 9 81 326458 182261 7 74 95141 468079 8 51 17254 35435 3 85 232992 429217 5 21 322232 113709 8 94 290870 95148 3 39 436099 266272 6 18 155735 195464 5 57 425279 330426 9 87 458100 189664 4 7...
output:
101011001000100011010111100000000001100001000010001010000000010000101001100001101011000000000001011000000000010000100000101000001000001010111001100010111001100100101001010010101001110101001000011010110100000000000011000111000011100010101000011011101001010000000000000110001000111010000010010010010000...
result:
ok single line: '101011001000100011010111100000...1000011010000010000101011000100'
Test #11:
score: 0
Accepted
time: 283ms
memory: 130216kb
input:
1 500000 500000 500000 463657 271762 1554 33 268462 416602 752 57 232884 291386 934 86 156239 192958 988 45 456182 465291 748 92 293901 200213 1764 35 400287 114393 1883 21 66445 186455 1936 72 256226 412499 235 53 118804 2424 556 48 217585 398265 1246 25 407376 105528 1711 66 437274 219222 268 60 2...
output:
100000000011001001000000000010100001000000100000000000100000000000111000000000001001010001100000100010100100110010010001010100100000100001001011010000100000000001001000001000000010001001010000000100000100010000001100000000000110100011100011000000000001100101000010100001000000000100011000011011000001...
result:
ok single line: '100000000011001001000000000010...0010011000010010110000100000000'
Test #12:
score: 0
Accepted
time: 320ms
memory: 117500kb
input:
1 200000 500000 390113 167473 53087 7 40 127766 31485 3 77 122178 73725 4 280 165130 187689 8 22 160640 31022 5 54 49941 108757 8 254 51900 63848 2 273 198039 105397 1 65 93834 156249 3 37 75775 72556 2 34 180908 4310 4 2088433 151872 97064 9 2866315 67375 4359 10 52 586 177196 4 16 79615 91304 9 19...
output:
110011000100010111000011111100001111100011011111110010001101100100110000110100111101101110101110011001101001000001111010011111100001101001101110110101110000001010100010011001010110100010000001101000010011100111000101011000111001011111001011101000100101100001101001010011101100011011011110000010011011...
result:
ok single line: '110011000100010111000011111100...1101010101101100101011001110001'
Test #13:
score: 0
Accepted
time: 331ms
memory: 120872kb
input:
1 200000 500000 500000 61211 118103 144 81836 13561 22617 1166 402 173146 85997 505 163 32172 185229 1321 5 41738 20077 411 2855263 178084 192923 989 4 106963 88155 633 80 195732 105926 856 98 79684 164339 1574 14 17805 63626 1763 3746238 62051 33869 1417 315 94813 102630 125 57 117507 184986 633 18...
output:
110000110011001110011000101001000100100100000101010001100010001001100000100001000010100000000100001000100000100011010100010001001000000011001010100010000111000000000000110000110000001000010010011100000000000000001010001110010000000000000010100010100000000001110010011110000001001001000011000100101010...
result:
ok single line: '110000110011001110011000101001...0000001000110100110110100000000'
Test #14:
score: 0
Accepted
time: 343ms
memory: 130628kb
input:
1 500000 500000 500000 420052 355289 2 2 309678 317458 8 11 61704 8266 7 70 296113 396246 3 83 475788 162969 5 93 22424 181415 9 7 480390 28262 1 10 380549 78679 8 13 152190 61422 8 31 259056 208854 8 4 138165 249290 10 58 57100 212361 9 82 106575 201277 2 13 73829 439668 6 62 140443 219369 8 5 1078...
output:
100001101101011110010011011011101110111100011101010110110111010010011110110100111101010001001011111110100111001100011011011111111001101101010110111001110101100100111101011110111110111100000011001011100011111011111111111100110011110110100101000100001111111010100101111001001010101111000000011111011010...
result:
ok single line: '100001101101011110010011011011...1111101111110011101100111111111'
Test #15:
score: 0
Accepted
time: 300ms
memory: 131412kb
input:
1 500000 500000 500000 270234 117804 1782 59 487444 34087 1664 66 289462 489609 781 27 41700 352509 1870 14 218553 6119 572 97 215144 2258 1486 58 229758 75287 650 96 390152 474120 781 78 281060 391879 845 72 212023 73757 845 43 175436 194520 737 47 385899 101608 887 85 398726 250221 1429 62 67802 7...
output:
110100100100000100010100000000000110100101000000001000101010100000000010100011100000111010100001000001000011101100110101111001000010010111101001000010000011000000001100100000011001000010100100000101001011000000100101000101000010000001101100111100000000010000000010010010011001001100000000001110001001...
result:
ok single line: '110100100100000100010100000000...0100000000001010000000000000010'
Test #16:
score: 0
Accepted
time: 210ms
memory: 117060kb
input:
1 250002 500000 500000 1 2 1 115683844 2 250002 1 850281965 1 3 1 900000009 3 250002 1 854267056 1 4 1 444184972 4 250002 1 851353302 1 5 1 314211665 5 250002 1 863294696 1 6 1 900000009 6 250002 1 874026313 1 7 1 900000009 7 250002 1 840010136 1 8 1 496150051 8 250002 1 899450367 1 9 1 900000009 9 ...
output:
110110010000101110010111111100011010001000101110111110011111011000001111101110111111000010000011000111111101011001011011111111110110100010101000000000010100000101101001110000010100011011001100001110000101100000111000010000010101110101100001101111100110001111011000010110101110111111011000100001100110...
result:
ok single line: '110110010000101110010111111100...0110001100011010100010101011011'
Test #17:
score: 0
Accepted
time: 364ms
memory: 145780kb
input:
1 500000 499999 500000 1 2 1 900000001 2 3 1 889793906 2 4 1 866671124 2 5 1 845385183 2 6 1 851253005 2 7 1 810344594 2 8 1 891357151 2 9 1 880320997 2 10 1 838371291 2 11 1 835447460 2 12 1 863553591 2 13 1 856806584 2 14 1 856885463 2 15 1 852192684 2 16 1 891121453 2 17 1 811660786 2 18 1 879481...
output:
111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1110111111111111111111111111111'
Test #18:
score: 0
Accepted
time: 124ms
memory: 75996kb
input:
1 200000 379990 1 1 20001 1 1 2 20002 1 1 3 20003 1 1 4 20004 1 1 5 20005 1 1 6 20006 1 1 7 20007 1 1 8 20008 1 1 9 20009 1 1 10 20010 1 1 11 20011 1 1 12 20012 1 1 13 20013 1 1 14 20014 1 1 15 20015 1 1 16 20016 1 1 17 20017 1 1 18 20018 1 1 19 20019 1 1 20 20020 1 1 21 20021 1 1 22 20022 1 1 23 20...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #19:
score: 0
Accepted
time: 106ms
memory: 8300kb
input:
1110 40 95 1 19 14 1 150549 2 10 1 19135 21 6 1 8701 2 13 1 212600 13 1 1 69485 10 14 1 294969 20 1 1 24409 17 20 1 42742 5 32 1 65281 4 27 1 11420 38 22 1 43570 35 37 1 49746 9 10 1 111214 7 23 1 23544 36 31 1 19452 11 29 1 98384 29 22 1 71471 5 19 1 6608 35 8 1 113985 9 19 1 34266 5 24 1 6450 3 11...
output:
1111111111111111111111111111111111111111 1111111111111111111111111111111111111111 1001110001110000000001001010000001000001000 1111111111111111010110111111111111111111111 100000010000000001000100100000001000110000000 101000111011100000011100100001111101001011000 11100100100001000010000000000000000010...
result:
ok 1110 lines
Test #20:
score: 0
Accepted
time: 291ms
memory: 104776kb
input:
1 200000 500000 1 2734 29417 1 41139 127119 99468 1 379168 177272 175151 1 136336 55538 44290 1 52788 90348 10738 1 97848 197405 54466 1 136512 27642 174241 1 512678 70765 75266 1 304618 36063 51863 1 69313 43655 14823 1 80107 2018 85483 1 652138 72681 173667 1 199816 7996 14887 1 251741 132987 1428...
output:
111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111111'
Test #21:
score: 0
Accepted
time: 195ms
memory: 107684kb
input:
1 500000 500000 1 254455 146143 1 96365 95795 300631 1 65917 284450 170980 1 69153 213595 108687 1 41751 375243 57417 1 55196 399661 480143 1 5626 103729 350468 1 55806 194862 341139 1 37046 321853 287363 1 12897 19593 443889 1 94102 201321 58781 1 72850 39865 150223 1 79172 428381 347804 1 33173 25...
output:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000001000000000000000000000000000000010000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000...
result:
ok single line: '100000000000000000000000000000...0000000001000000000000000000000'
Test #22:
score: 0
Accepted
time: 342ms
memory: 101744kb
input:
1 200000 500000 1 73293 11550 1 667 117149 144954 1 585 125562 80664 1 10460247 77431 134038 1 57766422 123969 19884 1 86 183588 139264 1 6131536 176596 73661 1 4763360 110460 115427 1 19311604 189793 117834 1 37752357 7754 130527 1 16439463 51497 16963 1 1817388 13691 86086 1 64713386 73657 171597 ...
output:
111111111011111011111111111111111111111011111110111101111111111111111111101111111111110011111011111110111111011101110111111111111111111111111111101101111111111011111111111111111111111111111111011111111111111111111111111111111111111111111111101111111111110111111111111111111111111111111111111111111101...
result:
ok single line: '111111111011111011111111111111...1111111111111111111111111111111'
Test #23:
score: 0
Accepted
time: 239ms
memory: 106316kb
input:
1 500000 500000 1 91812 173951 1 162 114291 23848 1 551 63225 357843 1 607 173752 314621 1 398 72184 442492 1 349 428608 344267 1 431 476581 260082 1 981 347555 439011 1 314 84077 440487 1 118 332472 318469 1 741 342071 439147 1 570 188106 411053 1 352 23205 225297 1 414 369067 273519 1 539 74851 40...
output:
110001101010010011111000000110111101000100001000011100111001110010111000110010001111110011010000110101101101011001000001111001000100100010011101100100010100011001001001001101101110111111000110011010001010010000010101111011010101000011111010100101010001010000011110000001111110011011010001010000000010...
result:
ok single line: '110001101010010011111000000110...1100110101011000101101101111011'
Extra Test:
score: 0
Extra Test Passed