Submission #370928

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370928	2021-02-25T05:52:10 Z	maroonrk	Comparing Plants (IOI20_plants)	C++17	100 / 100	1821 ms	101700 KB

plants

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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

template<class t>
void print(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t,class u>
void print(const pair<t,u>&p,int suc=1){
	print(p.a,2);
	print(p.b,suc);
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif
	return uniform_int_distribution<ll>(l, r)(gen);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

//atcoder-library をまあまあコピーして使っている

//N() が単位元

//merge で片方が inactive のときはもう片方をそのまま返す，
//といったときに，lazy の情報までコピーして渡さないようにする

//get の最後の引数は単位元と口では言いつつ・・・？
//たとえば min で最後の引数を 0 にしても 1 とかが返ってくることはある（一敗）

//VERIFY:
//https://atcoder.jp/contests/practice2/tasks/practice2_k
template<class N>
struct seglazy{
	vc<N> x;
	int L,s;
	seglazy(){}
	template<class T>
	seglazy(const vc<T>& a){
		int n=a.size();
		L=0;
		while((1<<L)<n)L++;
		s=1<<L;
		x.resize(s*2);
		rep(i,n)x[s+i]=N(a[i]);
		gnr(i,1,s)upd(i);
	}
	void upd(int i){
		x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void push(int i){
		x[i].push(x[i*2],x[i*2+1]);
	}
	N composite(int l,int r){
		assert(0<=l&&l<=r&&r<=s);
		if(l==r)return N();
		
		l+=s;
		r+=s;
		
		for (int i = L; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r - 1) >> i);
		}
		
		N sml,smr;
		while (l < r) {
			if (l & 1) sml = N::merge(sml, x[l++]);
			if (r & 1) smr = N::merge(x[--r], smr);
			l >>= 1;
			r >>= 1;
		}

		return N::merge(sml, smr);
	}
	template<class F,class... Args>
	void ch(int l, int r, F f,Args&&... args) {
		assert(0<=l&&l<=r&&r<=s);
		if (l == r) return;

		l+=s;
		r+=s;

		for (int i = L; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r - 1) >> i);
		}

		{
			int l2 = l, r2 = r;
			while (l < r) {
				if (l & 1){
					(x[l++].*f)(forward<Args>(args)...);
				}
				if (r & 1){
					(x[--r].*f)(forward<Args>(args)...);
				}
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}

		for (int i = 1; i <= L; i++) {
			if (((l >> i) << i) != l) upd(l >> i);
			if (((r >> i) << i) != r) upd((r - 1) >> i);
		}
	}
	N getall(){return x[1];}
	template <class F,class... Args> 
	pair<int,N> max_right(int l,F f,Args&&... args){
		assert(0<=l&&l<=s);
		if(l==s)return mp(s,N());
		l+=s;
		
		for (int i = L; i >= 1; i--) push(l >> i);
		N sm;
		assert((sm.*f)(forward<Args>(args)...));
		do {
			while (l % 2 == 0) l >>= 1;
			if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
				while (l < s) {
					push(l);
					l = (2 * l);
					N tmp=N::merge(sm,x[l]);
					if ((tmp.*f)(forward<Args>(args)...)) {
						sm = tmp;
						l++;
					}
				}
				return mp(l - s,sm);
			}
			sm = N::merge(sm, x[l]);
			l++;
		} while ((l & -l) != l);
		return mp(s,sm);
	}
	//XXI Opencup Krakow M
	template <class F,class... Args> 
	pair<int,N> min_left(int r,F f,Args&&... args){
		assert(0<=r&&r<=s);
        if(r==0)return mp(0,N());
        r+=s;
        for (int i = L; i >= 1; i--) push((r - 1) >> i);
        N sm;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
                while (r < s) {
                    push(r);
                    r = (2 * r + 1);
                    N tmp=N::merge(x[r],sm);
                    if ((tmp.*f)(forward<Args>(args)...)) {
                        sm = tmp;
                        r--;
                    }
                }
                return mp(r + 1 - s,sm);
            }
            sm = N::merge(x[r], sm);
        } while ((r & -r) != r);
        return mp(0,sm);
    }
	template<class F,class...Args>
	void point_change(int p,F f,Args&&...args){
		assert(0 <= p && p < s);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		(x[p].*f)(forward<Args>(args)...);
		for (int i = 1; i <= L; i++) upd(p >> i);
	}
	N point_get(int p){
		assert(0 <= p && p < s);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		return x[p];
	}
	void point_set(int p,N val){
		assert(0 <= p && p < s);
		p += s;
		for (int i = L; i >= 1; i--) push(p >> i);
		x[p]=val;
		for (int i = 1; i <= L; i++) upd(p >> i);
	}
	void enumerater(int l,int r,int i,int b,int e,vc<N>&dst){
		if(e<=l||r<=b)
			return;
		if(l+1==r){
			dst.pb(x[i]);
			return;
		}
		push(i);
		int m=(l+r)/2;
		enumerater(l,m,i*2,b,e,dst);
		enumerater(m,r,i*2+1,b,e,dst);
	}
	void enumerate(int b,int e,vc<N>&dst){
		assert(b<=e);
		return enumerater(0,s,1,b,e,dst);
	}
};

//Range add,min
struct N{
	int lz,mn;
	N(int v=inf):lz(0),mn(v){}
	void add(int v){
		mn+=v;
		lz+=v;
	}
	void push(N&x,N&y){
		x.add(lz);
		y.add(lz);
		lz=0;
	}
	static N merge(N x,N y){
		return N(min(x.getm(),y.getm()));
	}
	int getm(){return mn;}
	bool ok(int v){
		return mn>v;
	}
};

//VERIFY: yosupo
//CF Global3 H
//ARC073 F
//point update
template<class T,class F>
struct SegTree{
	vc<T> buf;
	int s;
	const F f;
	const T g;
	SegTree(F ff,T gg):f(ff),g(gg){}
	void init(const vc<T>& d){
		int n=d.size();
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,g);
		rep(i,n)
			buf[i+s]=d[i];
		gnr(i,1,s)
			u(i);
	}
	SegTree(const vc<T>& d,F ff,T gg):f(ff),g(gg){
		init(d);
	}
	void u(int i){
		buf[i]=f(buf[i*2],buf[i*2+1]);
	}
	void set(int i,T t){
		i+=s;
		buf[i]=t;
		while(i>>=1)u(i);
	}
	void upd(int i,T t){
		i+=s;
		buf[i]=f(buf[i],t);
		while(i>>=1)u(i);
	}
	T get(int b,int e,int l,int r,int i){
		if(e<=l||r<=b)return g;
		if(b<=l&&r<=e)return buf[i];
		int m=(l+r)/2;
		return f(get(b,e,l,m,i*2),get(b,e,m,r,i*2+1));
	}
	T get(int b,int e){
		return get(b,e,0,s,1);
	}
};
template<class T,class F>
SegTree<T,F> segtree(const vc<T>& d,F f,T g){
	return SegTree<T,F>(d,f,g);
}
const auto pimin=[](pi a,pi b){return min(a,b);};
const auto pimax=[](pi a,pi b){return max(a,b);};

int n,k;

struct SUB{
	vi a;
	int h;
	vvc<int> z;
	void init(vi aa){
		a=aa;
		auto seg=segtree(vc<pi>(n,pi(-1,-1)),pimax,pi(-1,-1));
		vi p(n);
		rep(i,n)p[a[i]]=i;
		vi d(n,-1);
		for(auto x:p){
			int l=x+1,r=x+k;
			pi mx(-1,-1);
			chmax(mx,seg.get(l,min(r,n)));
			if(n<r)chmax(mx,seg.get(0,r-n));
			if(mx.b!=-1){
				d[x]=(mx.b-x+n)%n;
			}
			seg.set(x,pi(a[x],x));
		}
		h=__lg(n)+1;
		z.resize(h,vi(n,-1));
		z[0]=d;
		rng(lv,1,h){
			rep(i,n){
				int j=z[lv-1][i];
				if(j!=-1){
					int w=z[lv-1][(i+j)%n];
					if(w!=-1){
						z[lv][i]=j+w;
					}
				}
			}
		}
	}
	bool reach(int x,int y){
		assert(a[x]>=a[y]);
		int d=(y-x+n)%n;
		per(lv,h){
			int w=z[lv][x];
			if(w!=-1&&w<=d){
				x=(x+w)%n;
				d-=w;
			}
		}
		return d<k&&a[x]>=a[y];
	}
} sub[2];

vi rw;

void init(signed k_, std::vector<signed> input){
	n=si(input);
	k=k_;
	
	vi a(n);
	
	seglazy<N> x(input),y(input);
	per(val,n){
		while(1){
			int i=x.max_right(0,&N::ok,0).a;
			if(i<n){
				x.ch(i,i+1,&N::add,ten(9));
				int l=i+1,r=i+k;
				y.ch(l,min(r,n),&N::add,1);
				if(n<r)y.ch(0,r-n,&N::add,1);
			}else break;
		}
		{
			int i=y.max_right(0,&N::ok,0).a;
			assert(i<n);
			a[i]=val;
			y.ch(i,i+1,&N::add,ten(9));
			{
				int l=i+1-k,r=i;
				x.ch(max(l,int(0)),r,&N::add,-1);
				y.ch(max(l,int(0)),r,&N::add,-1);
				if(l<0){
					x.ch(n+l,n,&N::add,-1);
					y.ch(n+l,n,&N::add,-1);
				}
			}
			{
				int l=i+1,r=i+k;
				y.ch(l,min(r,n),&N::add,-1);
				if(n<r)y.ch(0,r-n,&N::add,-1);
			}
		}
	}
	rep(w,2){
		sub[w].init(a);
		reverse(all(a));
	}
	
	rw=a;
}

signed compare_plants(signed x, signed y){
	int w=1;
	if(rw[x]<rw[y]){
		swap(x,y);
		w=-1;
	}
	int ans=0;
	if(sub[0].reach(x,y))ans=1;
	if(sub[1].reach(n-1-x,n-1-y))ans=1;
	return ans*w;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	67 ms	3180 KB	Output is correct
7	Correct	209 ms	11980 KB	Output is correct
8	Correct	960 ms	97864 KB	Output is correct
9	Correct	973 ms	97700 KB	Output is correct
10	Correct	1033 ms	97916 KB	Output is correct
11	Correct	1059 ms	97788 KB	Output is correct
12	Correct	1101 ms	97700 KB	Output is correct
13	Correct	1159 ms	97788 KB	Output is correct
14	Correct	1168 ms	97700 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	6 ms	748 KB	Output is correct
7	Correct	110 ms	6760 KB	Output is correct
8	Correct	3 ms	492 KB	Output is correct
9	Correct	8 ms	748 KB	Output is correct
10	Correct	115 ms	6752 KB	Output is correct
11	Correct	128 ms	6760 KB	Output is correct
12	Correct	127 ms	6752 KB	Output is correct
13	Correct	109 ms	6704 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	6 ms	748 KB	Output is correct
7	Correct	110 ms	6760 KB	Output is correct
8	Correct	3 ms	492 KB	Output is correct
9	Correct	8 ms	748 KB	Output is correct
10	Correct	115 ms	6752 KB	Output is correct
11	Correct	128 ms	6760 KB	Output is correct
12	Correct	127 ms	6752 KB	Output is correct
13	Correct	109 ms	6704 KB	Output is correct
14	Correct	241 ms	14240 KB	Output is correct
15	Correct	1800 ms	101700 KB	Output is correct
16	Correct	220 ms	14092 KB	Output is correct
17	Correct	1819 ms	101500 KB	Output is correct
18	Correct	1380 ms	101136 KB	Output is correct
19	Correct	1410 ms	101500 KB	Output is correct
20	Correct	1807 ms	101620 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	114 ms	3816 KB	Output is correct
4	Correct	1206 ms	100648 KB	Output is correct
5	Correct	1307 ms	100860 KB	Output is correct
6	Correct	1587 ms	101136 KB	Output is correct
7	Correct	1684 ms	101500 KB	Output is correct
8	Correct	1821 ms	101640 KB	Output is correct
9	Correct	1197 ms	101000 KB	Output is correct
10	Correct	1225 ms	101012 KB	Output is correct
11	Correct	1138 ms	100732 KB	Output is correct
12	Correct	1231 ms	100972 KB	Output is correct
13	Correct	1349 ms	100848 KB	Output is correct

Subtask #5

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	620 KB	Output is correct
7	Correct	24 ms	1388 KB	Output is correct
8	Correct	26 ms	1388 KB	Output is correct
9	Correct	21 ms	1388 KB	Output is correct
10	Correct	20 ms	1388 KB	Output is correct
11	Correct	19 ms	1388 KB	Output is correct
12	Correct	21 ms	1388 KB	Output is correct
13	Correct	18 ms	1388 KB	Output is correct

Subtask #6

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	4 ms	620 KB	Output is correct
6	Correct	1126 ms	100220 KB	Output is correct
7	Correct	1375 ms	100220 KB	Output is correct
8	Correct	1480 ms	100348 KB	Output is correct
9	Correct	1744 ms	100600 KB	Output is correct
10	Correct	1050 ms	99964 KB	Output is correct
11	Correct	1269 ms	100500 KB	Output is correct
12	Correct	1002 ms	99964 KB	Output is correct
13	Correct	1106 ms	99964 KB	Output is correct
14	Correct	1380 ms	100604 KB	Output is correct
15	Correct	1582 ms	100372 KB	Output is correct
16	Correct	982 ms	99816 KB	Output is correct
17	Correct	1075 ms	100092 KB	Output is correct

Subtask #7

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	67 ms	3180 KB	Output is correct
7	Correct	209 ms	11980 KB	Output is correct
8	Correct	960 ms	97864 KB	Output is correct
9	Correct	973 ms	97700 KB	Output is correct
10	Correct	1033 ms	97916 KB	Output is correct
11	Correct	1059 ms	97788 KB	Output is correct
12	Correct	1101 ms	97700 KB	Output is correct
13	Correct	1159 ms	97788 KB	Output is correct
14	Correct	1168 ms	97700 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	512 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	6 ms	748 KB	Output is correct
21	Correct	110 ms	6760 KB	Output is correct
22	Correct	3 ms	492 KB	Output is correct
23	Correct	8 ms	748 KB	Output is correct
24	Correct	115 ms	6752 KB	Output is correct
25	Correct	128 ms	6760 KB	Output is correct
26	Correct	127 ms	6752 KB	Output is correct
27	Correct	109 ms	6704 KB	Output is correct
28	Correct	241 ms	14240 KB	Output is correct
29	Correct	1800 ms	101700 KB	Output is correct
30	Correct	220 ms	14092 KB	Output is correct
31	Correct	1819 ms	101500 KB	Output is correct
32	Correct	1380 ms	101136 KB	Output is correct
33	Correct	1410 ms	101500 KB	Output is correct
34	Correct	1807 ms	101620 KB	Output is correct
35	Correct	1 ms	364 KB	Output is correct
36	Correct	1 ms	364 KB	Output is correct
37	Correct	114 ms	3816 KB	Output is correct
38	Correct	1206 ms	100648 KB	Output is correct
39	Correct	1307 ms	100860 KB	Output is correct
40	Correct	1587 ms	101136 KB	Output is correct
41	Correct	1684 ms	101500 KB	Output is correct
42	Correct	1821 ms	101640 KB	Output is correct
43	Correct	1197 ms	101000 KB	Output is correct
44	Correct	1225 ms	101012 KB	Output is correct
45	Correct	1138 ms	100732 KB	Output is correct
46	Correct	1231 ms	100972 KB	Output is correct
47	Correct	1349 ms	100848 KB	Output is correct
48	Correct	1 ms	364 KB	Output is correct
49	Correct	1 ms	364 KB	Output is correct
50	Correct	1 ms	364 KB	Output is correct
51	Correct	1 ms	364 KB	Output is correct
52	Correct	1 ms	364 KB	Output is correct
53	Correct	3 ms	620 KB	Output is correct
54	Correct	24 ms	1388 KB	Output is correct
55	Correct	26 ms	1388 KB	Output is correct
56	Correct	21 ms	1388 KB	Output is correct
57	Correct	20 ms	1388 KB	Output is correct
58	Correct	19 ms	1388 KB	Output is correct
59	Correct	21 ms	1388 KB	Output is correct
60	Correct	18 ms	1388 KB	Output is correct
61	Correct	92 ms	5484 KB	Output is correct
62	Correct	177 ms	14092 KB	Output is correct
63	Correct	969 ms	100624 KB	Output is correct
64	Correct	1127 ms	100932 KB	Output is correct
65	Correct	1522 ms	101168 KB	Output is correct
66	Correct	1651 ms	101316 KB	Output is correct
67	Correct	1753 ms	101500 KB	Output is correct
68	Correct	1077 ms	100860 KB	Output is correct
69	Correct	1486 ms	101500 KB	Output is correct
70	Correct	1199 ms	100732 KB	Output is correct
71	Correct	1282 ms	100992 KB	Output is correct
72	Correct	1554 ms	101372 KB	Output is correct
73	Correct	1651 ms	101372 KB	Output is correct
74	Correct	1010 ms	100732 KB	Output is correct
75	Correct	1205 ms	100936 KB	Output is correct