QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#677578#9519. Build a Computerucup-team008#AC ✓257ms50476kbC++2317.5kb2024-10-26 12:58:402024-10-26 12:58:40

Judging History

This is the latest submission verdict.

  • [2024-10-26 12:58:40]
  • Judged
  • Verdict: AC
  • Time: 257ms
  • Memory: 50476kb
  • [2024-10-26 12:58:40]
  • Submitted

answer

// {{{ y0105w49 template 24K21
// hi mom
#ifndef NULL
#ifdef __GNUC__
#ifndef __clang__
// #include <bits/stdc++.h>
#include <bits/extc++.h>
#include <tr2/dynamic_bitset>
#define EXTS
#else
#ifdef ARST
#include <bits/clang++.h>
#else
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
// #include <cuchar>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
// #include <memory_resource>
#include <string_view>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
// #include <stop_token>
#include <semaphore>
// #include <source_location>
// #include <syncstream>
#include <version>
#endif
#if __cplusplus > 202002L
// #include <expected>
// #include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#endif
#endif
#endif
#else
#error "unsupported"
#endif
#endif
using namespace std;
#ifdef ARST
#define JO 1
#define OJ 0
#else
#define JO 0
#define OJ 1
#endif
#define STR(x) #x
#define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true)
#define Wsave GCCDIAG(push)
#define Wpop GCCDIAG(pop)
#define Wsupp(w) GCCDIAG(ignored "-W" w)
#define Wpush(w) Wsave; Wsupp(w)
#define typeof __typeof__
namespace gbd_ns {
	template<typename C> struct is_iterable {
		template<class T> static long check(...);
		template<class T> static char check(int,typename T::const_iterator = C().end());
		enum {
			value = sizeof(check<C>(0)) == sizeof(char),
			neg_value = sizeof(check<C>(0)) != sizeof(char)
		};
	};
	template<class T> struct _gbd3C;
	template<class T> ostream &_gbd3(ostream &os,const T &x) { return _gbd3C<T>::call(os,x); }
	template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'<<x<<'"'; }
	template<> ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'<<x<<'"'; }
	template<class T> ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); }
	template<class A,class B> ostream &_gbd4(ostream &os,const pair<A,B> &p) {
		_gbd3(os<<'(',p.first);
		_gbd3(os<<',',p.second);
		return os<<')';
	}
	template<class T,size_t N> struct _gbd4_tupleC {
		static void call(ostream &os,const T &t) {
			_gbd4_tupleC<T,N-1>::call(os,t);
			os<<','<<get<N-1>(t);
		}
	};
	template<class T> struct _gbd4_tupleC<T,1> {
		static void call(ostream &os,const T &t) { os<<get<0>(t); }
	};
	template<typename... Types> ostream &_gbd4(ostream &os,const tuple<Types...> &t) {
		os<<'(';
		_gbd4_tupleC<tuple<Types...>,sizeof...(Types)>::call(os,t);
		return os<<')';
	}
	template<> ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; }
	template<class T> ostream &_gbd4(ostream &os,const T &x) {
		return os<<x;
	}
	template<class T> struct _gbd3C {
		template<class U=T> static ostream &call(ostream &os,enable_if_t<is_iterable<U>::value,const T> &V) {
			os<<"{";
			bool ff=0;
			for(const auto &E:V) _gbd3_5<decltype(E)>(ff?os<<",":os,E), ff=1;
			return os<<"}";
		}
		template<class U=T> static ostream &call(ostream &os,enable_if_t<is_iterable<U>::neg_value,const T> &x) {
			return _gbd4(os,x);
		}
	};
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool,vector<string>::iterator nm,const T &x,Args&&... args);
	ostream &_gbd2(ostream &os,bool,vector<string>::iterator) { return os; }
	template<typename... Args> ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const char *x,Args&&... args) {
		return _gbd2(os<<(fi?"":"  ")<<x,0,nm+1,args...);
	}
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const T &x,Args&&... args) {
		return _gbd2(_gbd3<T>(os<<(fi?"":"  ")<<*nm<<"=",x),0,nm+1,args...);
	}
	vector<string> split(string s) {
		vector<string> Z;
		string z="";
		s+=',';
		int dep=0;
		for(char c:s) {
			if(c==',' && !dep) Z.push_back(z),z="";
			else z+=c;
			if(c=='(' || c=='{' || c=='[') ++dep;
			if(c==')' || c=='}' || c==']') --dep;
		}
		return Z;
	}
	template<typename... Args> ostream &_gbd1(ostream &os,const string &nm,Args&&... args) {
		return _gbd2(os,1,split(nm).begin(),args...);
	}
	template<typename... Args> string _gbd1(const string &nm,Args&&... args) {
		ostringstream oss;
		_gbd2(oss,1,split(nm).begin(),args...);
		return oss.str();
	}
}
bool DBG=1,EMACS=0;
#define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"<<endl:cerr)
#define dbgt(...) dbg(fmt_time(),__VA_ARGS__)
#define fmt(...) gbd_ns::_gbd1(#__VA_ARGS__,__VA_ARGS__)
template<class Fun> struct _y_combinator_result {
	Fun _fun;
	template<class T> explicit _y_combinator_result(T &&fun) : _fun(forward<T>(fun)) {}
	template<typename... Args> decltype(auto) operator()(Args&&... args) {
		return _fun(ref(*this),forward<Args>(args)...);
	}
};
template<class Fun> [[nodiscard]] decltype(auto) fix(Fun &&fun) {
	return _y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}
#define nop void()
#define sz(x) (int((x).size()))
#define all(v) (v).begin(),(v).end()
#define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k)
#define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k)
#define get(x,i) get<i>(x)
template<class T> T &smin(T &x,const T &y) { return y<x?x=y:x; }
template<class T> T &smax(T &x,const T &y) { return y>x?x=y:x; }
template<class T> bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; }
template<class T> bool cinb(const T &x,const T &l,const T &r) { return l<=r?l<=x&&x<=r:l<=x||x<=r; }
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
template<template<class> class C,class T> T popv(C<T> &v) { T z=v.back(); v.pop_back(); return z; }
template<template<class> class C,class T> T popq(C<T> &v) { T z=v.top(); v.pop(); return z; }
template<template<class> class C,class T> T pops(C<T> &v) { T z=*v.begin(); v.erase(v.begin()); return z; }
template<template<class,class> class C,class K,class V> pair<K,V> popm(C<K,V> &v) { pair<K,V> z=*v.begin(); v.erase(v.begin()); return z; }
template<template<class> class C,class T> void erase1(C<T> &v,const T &x) { v.erase(v.find(x)); }
template<template<class> class C,class T> int lbi(C<T> &v,const T &x) { return int(lower_bound(all(v),x)-v.begin()); }
template<template<class> class C,class T> int findi(C<T> &v,const T &x) { auto it=lower_bound(all(v),x); return it!=v.end()&&*it==x?int(it-v.begin()):-1; }
template<class V> int sortu(V &v) { sort(all(v)); int z=int(unique(all(v))-v.begin()); v.resize(z); return z; }
template<typename T,typename... Args> T tee(T (*f)(Args... args),Args&&... args) { T z=f(forward<Args>(args)...); cout<<z<<endl; return z; }
template<typename... Args> void tee(void (*f)(Args... args),Args&&... args) { f(forward<Args>(args)...); }
#ifdef EXTS
template<class S,class T> using omap=__gnu_pbds::tree<S,T,less<S>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<class T> using oset=omap<T,__gnu_pbds::null_type>;
template<class T> using rope=__gnu_cxx::rope<T>;
using dbitset=tr2::dynamic_bitset<>;
#endif
constexpr int e0=1, e1=10, e2=100, e3=1000;
constexpr int e4=10*e3, e5=100*e3, e6=1000*e3;
constexpr int e7=10*e6, e8=100*e6, e9=1000*e6;
constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9;
constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12;
constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15;
constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18;
constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27;
using ulll=__uint128_t;
using lll=__int128_t;
using ull=unsigned long long;
using ll=long long;
using uint=unsigned int;
using ushort=unsigned short;
using uchar=char;
using ld=long double;
#ifdef EXTS
using lld=__float128;
#endif
long long START_TIME=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();
inline long long now_U_03BC_s() { return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; }
const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; }
#define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0)
int arg1; bool inp; vector<string> args;
unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5);
mt19937 igen(seed<<1),gen(seed<<1|1);
#define irand(...) (assert(!inp),_rand(igen,__VA_ARGS__))
#define rand(...) _rand(gen,__VA_ARGS__)
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution<T>(l,r)(g); }
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); }
[[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits<int>::max()); }
template<class T> enable_if_t<numeric_limits<T>::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution<T>(l,r)(g); }
bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); }
template<class T> T _rand(mt19937 &g,initializer_list<T> il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); }
template<class T> T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; }
template<class T> T _rand(mt19937 &g,initializer_list<T> il,initializer_list<double> wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution<int>(wt)(g)); }
#define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle")
#define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop))
#define inr(x,...) ine(x,irand(__VA_ARGS__))
#define endl '\n'
string garb;
void exit0() { DBG=1; dbgt("gg (early)",seed); exit(0); }
#ifndef MAIN
#define MAIN _main
#endif
void MAIN();
int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit);
	arg1=0,args={argv,argv+argc};
	if(sz(args)>1) {
		if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin);
		else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin);
		else arg1=stoi(args[1]);
	}
	inp=!arg1;
	if(JO && getenv("EMACS")) EMACS=1;
	dbgt(arg1,seed,args);
	#ifdef QUIET
	DBG=0;
	#endif
	MAIN();
	DBG=1;
	dbgt("gg;wp",seed);
	return 0;
}
constexpr int inf=e9+99;
constexpr ll linf=1LL*e9*e9+99;
#if __cplusplus >= 202002L
constexpr long double U_03C4__ld=2*numbers::pi_v<long double>;
#else
const long double U_03C4__ld=2*acosl(-1);
#endif
#define U_03C4_ ((flt)U_03C4__ld)
constexpr long double U_03B5__ld=1e-8l;
#define U_03B5_ ((flt)U_03B5__ld)
// }}}
using flt=double; //CARE
constexpr int P=e9+7;//998'244'353;

string bin(int x) {
	string s="";
	for(;x;) s+=char('0'+x%2), x/=2;
	reverse(all(s));
	return s;
}
int nxt=0;
int alloc() { return ++nxt; }
vector<pair<int,int>> adj[1<<18];

void build_dumb(int l,int r,int src,int snk) {
	if(l>r) return;
	assert(2<=l && l<=r && r<=20);
	int u=alloc();
	adj[src].pb({u,1});
	for(int i=2;i<=r;i++) {
		if(i>=l) adj[u].pb({snk,0}), adj[u].pb({snk,1});
		if(i==r) break;
		int v=alloc();
		adj[u].pb({v,0}), adj[u].pb({v,1});
		u=v;
	}
}



void build(string L,string R,int src,int snk) {
	assert(L[0]=='1');
	assert(R[0]=='1');
	int n=sz(L); assert(n==sz(R));
	int lo=-1,mid=-1,hi=-1,both=src;

	for(int i=0;i<n;i++) {
		int nlo=-1,nmid=-1,nhi=-1,nboth=-1;

		if(~lo) nlo=i==n-1?snk:alloc(), adj[lo].pb({nlo,L[i]-'0'});
		if(~hi) nhi=i==n-1?snk:alloc(), adj[hi].pb({nhi,R[i]-'0'});
		if(~mid) nmid=i==n-1?snk:alloc(), adj[mid].pb({nmid,0}), adj[mid].pb({nmid,1});
		if(~both && L[i]==R[i]) nboth=i==n-1?snk:alloc(), adj[both].pb({nboth,L[i]-'0'});

		if(~lo && L[i]=='0') {
			if(!~nmid) nmid=i==n-1?snk:alloc();
			adj[lo].pb({nmid,1});
		}
		if(~hi && R[i]=='1') {
			if(!~nmid) nmid=i==n-1?snk:alloc();
			adj[hi].pb({nmid,0});
		}
		if(~both && L[i]!=R[i]) {
			if(!~nlo) nlo=i==n-1?snk:alloc();
			if(!~nhi) nhi=i==n-1?snk:alloc();
			adj[both].pb({nlo,0});
			adj[both].pb({nhi,1});
		}

			lo=nlo,mid=nmid,hi=nhi,both=nboth;
	}
}

int bb(string L,string R,int snk) {
static map<pair<string,string>,int> dp;
if(dp.count({L,R})) return dp[{L,R}];
	int src=alloc();
	dp[{L,R}]=src;
	dbg("bb",L,R,src,snk);
	assert(sz(L));
	assert(sz(R));
	assert(sz(L)<=sz(R));
	if(sz(L)==sz(R)) assert(L<=R);

	if(sz(L)==1) {
		if(L[0]=='0') {
			adj[src].pb({snk,0});
			if(sz(R)>1 || R[0]=='1') adj[src].pb({snk,1});
		} else if(L[0]=='1') {
			adj[src].pb({snk,1});
		} else assert(0);
		if(sz(R)==1) return src;
		L="00";
	}

	dbg(L,R);
	if(sz(L)==sz(R) && L[0]==R[0]) {
		adj[src].pb({bb(L.substr(1),R.substr(1),snk),L[0]-'0'});
		return src;
	}
	if(sz(L)==sz(R)) {
		int u=bb(L.substr(1),string(sz(L)-1,'1'),snk);
		adj[src].pb({u,0});
		u=bb(string(sz(R)-1,'0'),R.substr(1),snk);
		adj[src].pb({u,1});
		return src;
	}

	// int u0=alloc();
	// adj[src].pb({u0,0});
	// int u1=alloc();
	// adj[src].pb({u1,1});
	// int u0,u1;
	// if(L[0]=='0') u0=bb(L.substr(1),R.substr(1),snk);
	// else u0=bb(string(sz(L),'0'),R.substr(1),snk);
	// if(R[0]=='1') u1=bb(L.substr(1),R.substr(1),snk);
	// else u1=bb(L.substr(1),string(sz(R)-2,'1'),snk);
	int u0=bb(L[0]=='0'?L.substr(1):string(sz(L),'0'),R[0]=='0'?R.substr(1):string(sz(R)-1,'1'),snk);
	int u1=bb(L[0]=='1'?L.substr(1):string(sz(L)-1,'0'),R[0]=='1'?R.substr(1):string(sz(R)-2,'1'),snk);
	adj[src].pb({u0,0});
	adj[src].pb({u1,1});
	return src;
}


set<int> CC,sn;
void check(int u,int snk,int x=0) {
	sn.insert(u);
	if(u==snk) {
		assert(!CC.count(x));
		CC.insert(x);
		return;
	}
	for(auto [v,c]:adj[u]) {
		if(!x) assert(c);
		assert(inb(c,0,1));
		check(v,snk,x*2+c);
	}
}


auto solve() { /* CURSOR START */
	int l,r; inr(l,arg1), inr(r,l,arg1);
	string L=bin(max(l,2)),R=bin(r);
	dbg(l,r,L,R);

	int src=alloc();
	int snk=alloc();
	if(l==1) adj[src].pb({snk,1});
	if(r>1) {
		assert(L[0]=='1');
		assert(R[0]=='1');
		assert(sz(L)>=2);
		assert(sz(R)>=sz(L));
		adj[src].pb({bb(L.substr(1),R.substr(1),snk),1});
	}

	// bb(L.substr(1),R.substr(1),u,snk);
	// if(sz(L)==sz(R)) build(L,R,src,snk);
	// else {
	// 	build(L,string(sz(L),'1'),src,snk);
	// 	string lb(sz(R),'0'); lb[0]='1';
	// 	build(lb,R,src,snk);
	// 	build_dumb(sz(L)+1,sz(R)-1,src,snk);
	// }

	int n=nxt;
	dbg(n);
	assert(n<=100);
	static int indeg[122];
	for(int u=1;u<=n;u++) for(auto [v,c]:adj[u]) ++indeg[v];
	for(int u=1;u<=n;u++) assert(sz(adj[u])<=4);
	for(int u=1;u<=n;u++) if(u!=src) assert(indeg[u]);
	assert(!indeg[src]);
	for(int u=1;u<=n;u++) if(u!=snk) assert(sz(adj[u]));
	assert(!sz(adj[snk]));

	check(src,snk);
	assert(sz(sn)==n);
	assert(*sn.begin()==1);
	assert(*sn.rbegin()==n);
	assert(inb(src,1,n));
	assert(inb(snk,1,n));
	assert(*CC.begin()==l);
	assert(*CC.rbegin()==r);
	dbg(CC);
	// assert(sz(CC)==r-l+1);


	cout<<n<<endl;
	for(int u=1;u<=n;u++) {
		cout<<sz(adj[u]);
		// TODO: char nz
		for(auto [v,c]:adj[u]) cout<<' '<<v<<' '<<c;
		cout<<endl;
	}
	cout<<flush;
	assert(sz(CC)==r-l+1);
	dbgt(n);
}



void _main() { int NTC=1;
	// ine(NTC,5);
	for(int TC=1;TC<=NTC;TC++) {
		// cout<<"Case #"<<TC<<": ";
		tee(solve);
	}
	if(JO&&inp) assert((cin>>ws).eof());
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

input:

5 7

output:

5
1 3 1
0
2 4 0 5 1
1 2 1
2 2 0 2 1

result:

ok ok

Test #2:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

10 27

output:

8
1 3 1
0
2 4 0 8 1
2 5 0 7 1
2 6 0 6 1
2 2 0 2 1
4 2 0 2 1 6 0 6 1
2 7 0 6 1

result:

ok ok

Test #3:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

5 13

output:

6
1 3 1
0
2 4 0 6 1
3 2 1 5 0 5 1
2 2 0 2 1
3 2 0 2 1 5 0

result:

ok ok

Test #4:

score: 0
Accepted
time: 257ms
memory: 50476kb

input:

1 1000000

output:

39
2 2 1 3 1
0
4 2 0 2 1 4 0 22 1
4 2 0 2 1 5 0 5 1
4 2 0 2 1 6 0 6 1
4 2 0 2 1 7 0 7 1
4 2 0 2 1 8 0 8 1
4 2 0 2 1 9 0 9 1
4 2 0 2 1 10 0 10 1
4 2 0 2 1 11 0 11 1
4 2 0 2 1 12 0 12 1
4 2 0 2 1 13 0 13 1
4 2 0 2 1 14 0 14 1
4 2 0 2 1 15 0 15 1
4 2 0 2 1 16 0 16 1
4 2 0 2 1 17 0 17 1
4 2 0 2 1 18 0 1...

result:

ok ok

Test #5:

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

input:

1 1

output:

2
1 2 1
0

result:

ok ok

Test #6:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

7 9

output:

6
1 3 1
0
2 4 0 6 1
1 5 0
2 2 0 2 1
1 2 1

result:

ok ok

Test #7:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

3 7

output:

4
1 3 1
0
3 2 1 4 0 4 1
2 2 0 2 1

result:

ok ok

Test #8:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

1 5

output:

4
2 2 1 3 1
0
3 2 0 2 1 4 0
2 2 0 2 1

result:

ok ok

Test #9:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

1 4

output:

4
2 2 1 3 1
0
3 2 0 2 1 4 0
1 2 0

result:

ok ok

Test #10:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

8 9

output:

5
1 3 1
0
1 4 0
1 5 0
2 2 0 2 1

result:

ok ok

Test #11:

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

input:

7 51

output:

9
1 3 1
0
2 4 0 8 1
2 5 0 5 1
4 2 0 2 1 6 0 6 1
4 2 0 2 1 7 0 7 1
2 2 0 2 1
3 2 1 9 0 6 1
4 2 0 2 1 6 0 7 1

result:

ok ok

Test #12:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

51 79

output:

12
1 3 1
0
2 4 0 9 1
1 5 0
2 6 0 6 1
2 7 0 7 1
2 8 0 8 1
2 2 0 2 1
2 10 0 6 1
2 11 0 7 1
1 12 1
1 2 1

result:

ok ok

Test #13:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

92 99

output:

11
1 3 1
0
2 4 0 9 1
1 5 1
1 6 1
1 7 1
2 8 0 8 1
2 2 0 2 1
1 10 0
1 11 0
1 7 0

result:

ok ok

Test #14:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

27 36

output:

12
1 3 1
0
2 4 0 10 1
1 5 0
2 6 0 8 1
2 7 0 7 1
2 2 0 2 1
1 9 0
1 2 0
2 11 0 6 1
1 12 1
1 2 1

result:

ok ok

Test #15:

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

input:

55 84

output:

16
1 3 1
0
2 4 0 13 1
2 5 0 9 1
2 6 0 6 1
2 7 0 7 1
2 8 0 8 1
2 2 0 2 1
1 10 0
2 7 0 11 1
1 12 0
1 2 0
2 14 0 6 1
1 15 1
1 16 1
1 2 1

result:

ok ok

Test #16:

score: 0
Accepted
time: 182ms
memory: 33468kb

input:

297208 929600

output:

67
1 3 1
0
2 4 0 50 1
2 5 0 48 1
2 6 0 22 1
2 7 0 7 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
2 20 0 20 1
2 21 0 21 1
2 2 0 2 1
2 23 0 47 1
2 24 0 46 1
2 25 0 44 1
2 10 0 26 1
2 27 0 43 1
2 28 0 42 1
...

result:

ok ok

Test #17:

score: 0
Accepted
time: 103ms
memory: 29128kb

input:

45728 589156

output:

58
1 3 1
0
2 4 0 57 1
2 5 0 49 1
2 6 0 42 1
2 7 0 22 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
4 2 0 2 1 19 0 19 1
4 2 0 2 1 20 0 20 1
4 2 0 2 1 21 0 21 1
2 2 0 2 1
2 8 0 23 1
2 9 0 24 1
2 10 0 25 1
2 11 0 26 1
2...

result:

ok ok

Test #18:

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

input:

129152 138000

output:

39
1 3 1
0
2 4 0 32 1
1 5 0
1 6 0
1 7 0
2 8 0 20 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
2 2 0 2 1
2 9 0 21 1
1 22 0
2 11 0 23 1
2 12 0 24 1
1 25 0
1 26 0
1 27 0
2 16 0 28 1
1 29 0
1 30 0
1 31 0
1 2 0
1 33 1
...

result:

ok ok

Test #19:

score: 0
Accepted
time: 102ms
memory: 22796kb

input:

245280 654141

output:

62
1 3 1
0
2 4 0 52 1
2 5 0 45 1
2 6 0 22 1
2 7 0 7 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
2 20 0 20 1
4 2 0 2 1 21 0 21 1
2 2 0 2 1
2 7 0 23 1
2 8 0 24 1
2 9 0 25 1
2 10 0 26 1
2 11 0 27 1
2 28 0 ...

result:

ok ok

Test #20:

score: 0
Accepted
time: 21ms
memory: 7992kb

input:

202985 296000

output:

51
1 3 1
0
2 4 0 36 1
1 5 0
2 6 0 21 1
2 7 0 7 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
2 20 0 20 1
2 2 0 2 1
1 22 0
1 23 0
1 24 0
1 25 0
2 11 0 26 1
1 27 0
1 28 0
1 29 0
2 15 0 30 1
1 31 0
1 32 0
1 ...

result:

ok ok

Test #21:

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

input:

438671 951305

output:

68
1 3 1
0
2 4 0 22 1
2 5 0 5 1
2 6 0 6 1
2 7 0 7 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
2 20 0 20 1
2 21 0 21 1
2 2 0 2 1
2 23 0 53 1
2 6 0 24 1
2 25 0 50 1
2 8 0 26 1
2 9 0 27 1
2 28 0 49 1
2 29 ...

result:

ok ok

Test #22:

score: 0
Accepted
time: 88ms
memory: 18540kb

input:

425249 739633

output:

54
1 3 1
0
2 4 0 38 1
2 5 0 22 1
2 6 0 6 1
2 7 0 7 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
2 20 0 20 1
2 21 0 21 1
2 2 0 2 1
2 6 0 23 1
1 24 0
2 8 0 25 1
1 26 0
1 27 0
2 11 0 28 1
1 29 0
1 30 0
2 14...

result:

ok ok

Test #23:

score: 0
Accepted
time: 130ms
memory: 22804kb

input:

551207 961718

output:

56
1 3 1
0
2 4 0 39 1
2 5 0 38 1
2 6 0 37 1
2 7 0 34 1
1 8 1
1 9 1
2 10 0 32 1
1 11 1
2 12 0 31 1
2 13 0 29 1
1 14 1
2 15 0 28 1
2 16 0 26 1
1 17 1
2 18 0 25 1
2 19 0 22 1
1 20 1
1 21 1
1 2 1
2 23 0 23 1
2 24 0 24 1
2 2 0 2 1
2 22 0 22 1
2 27 0 27 1
2 25 0 25 1
2 26 0 26 1
2 30 0 30 1
2 28 0 28 1
2 ...

result:

ok ok

Test #24:

score: 0
Accepted
time: 106ms
memory: 26252kb

input:

114691 598186

output:

66
1 3 1
0
2 4 0 52 1
2 5 0 50 1
2 6 0 22 1
2 7 0 7 1
2 8 0 8 1
2 9 0 9 1
2 10 0 10 1
2 11 0 11 1
2 12 0 12 1
2 13 0 13 1
2 14 0 14 1
2 15 0 15 1
2 16 0 16 1
2 17 0 17 1
2 18 0 18 1
2 19 0 19 1
4 2 0 2 1 20 0 20 1
4 2 0 2 1 21 0 21 1
2 2 0 2 1
2 23 0 49 1
2 24 0 47 1
2 9 0 25 1
2 26 0 46 1
2 27 0 45...

result:

ok ok

Test #25:

score: 0
Accepted
time: 3ms
memory: 4464kb

input:

234654 253129

output:

44
1 3 1
0
1 4 1
1 5 1
2 6 0 32 1
2 7 0 30 1
1 8 1
2 9 0 28 1
1 10 1
2 11 0 27 1
2 12 0 25 1
1 13 1
2 14 0 24 1
2 15 0 20 1
1 16 1
1 17 1
1 18 1
1 19 1
2 2 0 2 1
2 21 0 21 1
2 22 0 22 1
2 23 0 23 1
2 19 0 19 1
2 20 0 20 1
2 26 0 26 1
2 24 0 24 1
2 25 0 25 1
2 29 0 29 1
2 27 0 27 1
2 31 0 31 1
2 28 0...

result:

ok ok

Test #26:

score: 0
Accepted
time: 11ms
memory: 6256kb

input:

554090 608599

output:

48
1 3 1
0
1 4 0
1 5 0
2 6 0 36 1
2 7 0 32 1
1 8 1
1 9 1
1 10 1
2 11 0 30 1
1 12 1
2 13 0 29 1
2 14 0 28 1
2 15 0 25 1
1 16 1
1 17 1
2 18 0 23 1
1 19 1
2 20 0 22 1
1 21 1
2 2 0 2 1
2 21 0 21 1
2 24 0 24 1
2 22 0 22 1
2 26 0 26 1
2 27 0 27 1
2 23 0 23 1
2 25 0 25 1
2 28 0 28 1
2 31 0 31 1
2 29 0 29 1...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed