Submission #1359359
Source Code Expand
//#pragma comment(linker, "/stack:20000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//
//#define _CRT_SECURE_NO_WARNINGS
//# include <iostream>
//# include <cmath>
//# include <algorithm>
//# include <stdio.h>
//# include <cstring>
//# include <string>
//# include <cstdlib>
//# include <vector>
//# include <bitset>
//# include <map>
//# include <queue>
//# include <ctime>
//# include <stack>
//# include <set>
//# include <list>
//# include <random>
//# include <deque>
//# include <functional>
//# include <iomanip>
//# include <sstream>
//# include <fstream>
//# include <complex>
//# include <numeric>
//# include <immintrin.h>
//# include <cassert>
//# include <array>
//
//using namespace std;
//
//// Let's define unordered map
//# ifdef __GNUC__
//# if __cplusplus > 199711L
//# include <unordered_set>
//# include <unordered_map>
//# else
//# include <tr1/unordered_map>
//# include <tr1/unordered_set>
//using namespace tr1;
//# endif
//# else
//# include <unordered_map>
//# include <unordered_set>
//# endif
//
//#define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
//#define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
//#define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
//#define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
//#define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
//#define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
//#define macro_dispatcher___(macro, nargs) macro ## nargs
//#define DBN1(a) cerr<<#a<<"="<<(a)<<"\n"
//#define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
//#define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
//#define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
//#define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
//#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
//#define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
//#define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
//#define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
//
//#ifdef _MSC_VER
//#define ALIGN(x) __declspec(align(x))
//#else
//#define ALIGN(x) __attribute__((aligned(x)))
//#endif
//
//#ifdef LOCAL
//#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
//#else
//#define CURTIME() ;
//#endif
//double __begin;
//#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
//
//#define mp make_pair
//typedef long long ll;
//typedef unsigned int uint;
//typedef unsigned long long ull;
//typedef pair<int, int> pii;
//typedef pair<long long, long long> pll;
//typedef vector<int> vi;
//typedef vector<long long> vll;
//typedef int itn;
//
//template<class T1, class T2, class T3>
//struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
//template<class T1, class T2, class T3>
//bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
//template<class T1, class T2, class T3>
//bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
//#define tri triple<int,int,int>
//#define trll triple<ll,ll,ll>
//
//#define FI(n) for(int i=0;i<n;++i)
//#define FJ(n) for(int j=0;j<n;++j)
//#define FK(n) for(int k=0;k<n;++k)
//#define FL(n) for(int l=0;l<n;++l)
//#define FQ(n) for(int q=0;q<n;++q)
//#define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
//#define all(a) std::begin(a), std::end(a)
//#define reunique(v) v.resize(unique(v.begin(), v.end()) - v.begin())
//
//#define sqr(x) ((x) * (x))
//#define sqrt(x) sqrt(1.0 * (x))
//#define pow(x, n) pow(1.0 * (x), n)
//
//#define COMPARE(obj) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b)
//#define COMPARE_BY(obj, field) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b) { return a.field < b.field; }
//
//#define checkbit(n, b) (((n) >> (b)) & 1)
//#define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
//#define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
//#define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
//inline int bits_count(int v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
//inline int bits_count(ll v){int t=v>>32;int p=(v& ((1LL << 32) - 1)); return bits_count(t) + bits_count(p); }
//unsigned int reverse_bits(register unsigned int x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
//template<class T>
//inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
//inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
//template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
//unsigned long long rdtsc() {
// unsigned long long ret;
// __asm__ __volatile__("rdtsc" : "=A" (ret) : :);
// return ret;
//}
//template<class T> T read_int() {
// const int B = 4096;
// static char b[B + 16], *i = b, *e = b + B;
// if (*i == 0) {
// memset(b, 0, B); cin.read(b, B); i = b;
// }
// while (*i && (*i < '0' || *i > '9')) {
// ++i;
// }
// T r = 0;
// while (*i >= '0' && *i <= '9') {
// r = r * 10 + *i - '0';
// ++i;
// if (i == e) {
// memset(b, 0, B); cin.read(b, B); i = b;
// }
// }
// ++i;
// return r;
//}
//template<class T>
//void write_int(T x, char endc = '\n') {
// const int B = 4096;
// static char outbuf[B + 20], *outp = outbuf, *loutp = outbuf + B;
// char* begp = outp;
// while (x) {
// T t = x / 10;
// char c = x - 10 * t + '0';
// *outp++ = c;
// x = t;
// }
// char* endp = outp - 1;
// while (begp < endp) {
// swap(*begp, *endp);
// ++begp;
// --endp;
// }
// if (outp > loutp) {
// cout.write(outbuf, outp - outbuf);
// outp = outbuf;
// }
// *outp++ = endc;
// struct F {
// F() {
// if (outp != outbuf) {
// cout.write(outbuf, outp - outbuf);
// }
// }
// };
// static F f;
//}
//
//
//
////STL output *****************************************************************************************************
//#define TT1 template<class T>
//#define TT1T2 template<class T1, class T2>
//#define TT1T2T3 template<class T1, class T2, class T3>
//TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
//TT1 ostream& operator << (ostream& os, const vector<T>& v);
//TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
//TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
//TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
//TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
//TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
//TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
//TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
//TT1 ostream& operator << (ostream& os, const vector<T>& v){ bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
//TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){ bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
//TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
//TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
//TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
//TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
//TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
//TT1T2 void printarray(T1 a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
//
////STL input *****************************************************************************************************
//TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
//TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
//TT1 inline istream& operator >> (istream& os, vector<T>& v) {
// if (v.size()) for (T& t : v) os >> t; else {
// string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
// stringstream ss(s); while (ss >> obj) v.push_back(obj);
// }
// return os;
//}
//TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
//
////Pair magic *****************************************************************************************************
//#define PT1T2 pair<T1, T2>
//TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
//TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
//
//#undef TT1
//#undef TT1T2
//#undef TT1T2T3
//
//#define FREIN(FILE) freopen(FILE, "rt", stdin)
//#define FREOUT(FILE) freopen(FILE, "wt", stdout)
//
//template<class T> bool isPrime(T x) { if (x < 2) return 0; for (T i = 2; i * i <= x; ++i) if (x % i == 0) return 0; return 1; }
//inline void normmod(ll &x, ll m) { x %= m; if (x < 0) x += m; }
//inline ll summodfast(ll x, ll y, ll m) { ll res = x + y; if (res >= m) res -= m; return res; }
//inline int summodfast(int x, int y, int m) { int res = x + y; if (res >= m) res -= m; return res; }
//inline void addmodfast(ll &x, ll y, ll m) { x += y; if (x >= m) x -= m; }
//inline void addmodfast(int &x, int y, int m) { x += y; if (x >= m) x -= m; }
//inline void submodfast(ll &x, ll y, ll m) { x -= y; if (x < 0) x += m; }
//inline void submodfast(int &x, int y, int m) { x -= y; if (x < 0) x += m; }
//inline ll mulmod(ll x, ll n, ll m){ ll res = 0; normmod(x, m); normmod(n, m); while (n){ if (n & 1) res = summodfast(res, x, m); x = summodfast(x, x, m); n >>= 1; } return res; }
//inline ll powmod(ll x, ll n, ll m){ ll res = 1; while (n){ if (n & 1)res = (res*x) % m; x = (x*x) % m; n >>= 1; }return res; }
//inline ll powmulmod(ll x, ll n, ll m){ ll res = 1; while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n >>= 1; } return res; }
//inline ll gcd(ll a, ll b){ ll t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
//inline int gcd(int a, int b){ int t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
//inline ll lcm(ll a, ll b){ return a / gcd(a, b)*b; }
//inline ll gcd(ll a, ll b, ll c){ return gcd(gcd(a, b), c); }
//inline int gcd(int a, int b, int c){ return gcd(gcd(a, b), c); }
//ll gcdex(ll a, ll b, ll& x, ll& y) {
// if (!a) { x = 0; y = 1; return b; }
// ll y1;
// ll d = gcdex(b % a, a, y, y1);
// x = y1 - (b / a) * y;
// return d;
//}
//
//// Useful constants
//
////int some_primes[10] = {24443, 100271, 500179, 1000003, 1000333, 2000321, 5000321, 98765431, 1000000123};
//#define INF 1011111111
//#define LLINF 1000111000111000111LL
//#define EPS (double)1e-10
//#define mod 1000000007
//#define PI 3.14159265358979323
//#define link asaxlajrewqwe
//#define rank wahayawehasdakw
////*************************************************************************************
//
//struct Interval {
// ll len;
// ll start;
// ll step;
// ll cnt;
//};
//
//int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
//#ifdef LOCAL
//// FREIN("input.txt");
//#endif
//
// ll n, k;
// cin >> n >> k;
// if (k == 1) {
// cout << 1 << endl;
// return 0;
// }
// if (k == 2) {
// cout << n << endl;
// return 0;
// }
// k -= 2;
// vector<Interval> v;
// int cur = 0;
// v.push_back({n - 2, 1, 0, 1});
// while (k > 0) {
//
// }
//
// return 0;
//}
//
//
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#define _CRT_SECURE_NO_WARNINGS
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
using namespace std;
// Let's define unordered map
# ifdef __GNUC__
# if __cplusplus > 199711L
# include <unordered_set>
# include <unordered_map>
# else
# include <tr1/unordered_map>
# include <tr1/unordered_set>
using namespace tr1;
# endif
# else
# include <unordered_map>
# include <unordered_set>
# endif
#define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
#define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
#define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
#define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
#define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
#define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
#define macro_dispatcher___(macro, nargs) macro ## nargs
#define DBN1(a) cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
#define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
#define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
#ifdef _MSC_VER
#define ALIGN(x) __declspec(align(x))
#else
#define ALIGN(x) __attribute__((aligned(x)))
#endif
#ifdef LOCAL
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#else
#define CURTIME() ;
#endif
double __begin;
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define mp make_pair
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef int itn;
template<class T1, class T2, class T3>
struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
template<class T1, class T2, class T3>
bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
template<class T1, class T2, class T3>
bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
#define tri triple<int,int,int>
#define trll triple<ll,ll,ll>
#define FI(n) for(int i=0;i<n;++i)
#define FJ(n) for(int j=0;j<n;++j)
#define FK(n) for(int k=0;k<n;++k)
#define FL(n) for(int l=0;l<n;++l)
#define FQ(n) for(int q=0;q<n;++q)
#define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
#define all(a) std::begin(a), std::end(a)
#define reunique(v) v.resize(unique(v.begin(), v.end()) - v.begin())
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(1.0 * (x))
#define pow(x, n) pow(1.0 * (x), n)
#define COMPARE(obj) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b)
#define COMPARE_BY(obj, field) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b) { return a.field < b.field; }
#define checkbit(n, b) (((n) >> (b)) & 1)
#define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
#define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
#define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
inline int bits_count(int v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
inline int bits_count(ll v){int t=v>>32;int p=(v& ((1LL << 32) - 1)); return bits_count(t) + bits_count(p); }
unsigned int reverse_bits(register unsigned int x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
template<class T>
inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
unsigned long long rdtsc() {
unsigned long long ret;
__asm__ __volatile__("rdtsc" : "=A" (ret) : :);
return ret;
}
template<class T> T read_int() {
const int B = 4096;
static char b[B + 16], *i = b, *e = b + B;
if (*i == 0) {
memset(b, 0, B); cin.read(b, B); i = b;
}
while (*i && (*i < '0' || *i > '9')) {
++i;
}
T r = 0;
while (*i >= '0' && *i <= '9') {
r = r * 10 + *i - '0';
++i;
if (i == e) {
memset(b, 0, B); cin.read(b, B); i = b;
}
}
++i;
return r;
}
template<class T>
void write_int(T x, char endc = '\n') {
const int B = 4096;
static char outbuf[B + 20], *outp = outbuf, *loutp = outbuf + B;
char* begp = outp;
while (x) {
T t = x / 10;
char c = x - 10 * t + '0';
*outp++ = c;
x = t;
}
char* endp = outp - 1;
while (begp < endp) {
swap(*begp, *endp);
++begp;
--endp;
}
if (outp > loutp) {
cout.write(outbuf, outp - outbuf);
outp = outbuf;
}
*outp++ = endc;
struct F {
F() {
if (outp != outbuf) {
cout.write(outbuf, outp - outbuf);
}
}
};
static F f;
}
//STL output *****************************************************************************************************
#define TT1 template<class T>
#define TT1T2 template<class T1, class T2>
#define TT1T2T3 template<class T1, class T2, class T3>
TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
TT1 ostream& operator << (ostream& os, const vector<T>& v);
TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
TT1 ostream& operator << (ostream& os, const vector<T>& v){ bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){ bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
TT1T2 void printarray(T1 a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
//STL input *****************************************************************************************************
TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
TT1 inline istream& operator >> (istream& os, vector<T>& v) {
if (v.size()) for (T& t : v) os >> t; else {
string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
stringstream ss(s); while (ss >> obj) v.push_back(obj);
}
return os;
}
TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
//Pair magic *****************************************************************************************************
#define PT1T2 pair<T1, T2>
TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
#undef TT1
#undef TT1T2
#undef TT1T2T3
#define FREIN(FILE) freopen(FILE, "rt", stdin)
#define FREOUT(FILE) freopen(FILE, "wt", stdout)
template<class T> bool isPrime(T x) { if (x < 2) return 0; for (T i = 2; i * i <= x; ++i) if (x % i == 0) return 0; return 1; }
inline void normmod(ll &x, ll m) { x %= m; if (x < 0) x += m; }
inline ll summodfast(ll x, ll y, ll m) { ll res = x + y; if (res >= m) res -= m; return res; }
inline int summodfast(int x, int y, int m) { int res = x + y; if (res >= m) res -= m; return res; }
inline void addmodfast(ll &x, ll y, ll m) { x += y; if (x >= m) x -= m; }
inline void addmodfast(int &x, int y, int m) { x += y; if (x >= m) x -= m; }
inline void submodfast(ll &x, ll y, ll m) { x -= y; if (x < 0) x += m; }
inline void submodfast(int &x, int y, int m) { x -= y; if (x < 0) x += m; }
inline ll mulmod(ll x, ll n, ll m){ ll res = 0; normmod(x, m); normmod(n, m); while (n){ if (n & 1) res = summodfast(res, x, m); x = summodfast(x, x, m); n >>= 1; } return res; }
inline ll powmod(ll x, ll n, ll m){ ll res = 1; while (n){ if (n & 1)res = (res*x) % m; x = (x*x) % m; n >>= 1; }return res; }
inline ll powmulmod(ll x, ll n, ll m){ ll res = 1; while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n >>= 1; } return res; }
inline ll gcd(ll a, ll b){ ll t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
inline int gcd(int a, int b){ int t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
inline ll lcm(ll a, ll b){ return a / gcd(a, b)*b; }
inline ll gcd(ll a, ll b, ll c){ return gcd(gcd(a, b), c); }
inline int gcd(int a, int b, int c){ return gcd(gcd(a, b), c); }
ll gcdex(ll a, ll b, ll& x, ll& y) {
if (!a) { x = 0; y = 1; return b; }
ll y1;
ll d = gcdex(b % a, a, y, y1);
x = y1 - (b / a) * y;
return d;
}
// Useful constants
//int some_primes[10] = {24443, 100271, 500179, 1000003, 1000333, 2000321, 5000321, 98765431, 1000000123};
#define INF 1011111111
#define LLINF 1000111000111000111LL
#define EPS (double)1e-10
#define mod 1000000007
#define PI 3.14159265358979323
#define link asaxlajrewqwe
#define rank wahayawehasdakw
//*************************************************************************************
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
// FREIN("input.txt");
#endif
string s;
cin >> s;
int ans = INF;
for (int c = 'a'; c <= 'z'; ++c) {
int tot = 0;
int cur = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != c) {
++cur;
} else {
tot = max(tot, cur);
cur = 0;
}
}
tot = max(tot, cur);
ans = min(ans, tot);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Shrinking |
User |
MrDindows |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
26639 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
0_03.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
1 ms |
256 KB |
1_03.txt |
AC |
1 ms |
256 KB |
1_04.txt |
AC |
1 ms |
256 KB |
1_05.txt |
AC |
1 ms |
256 KB |
1_06.txt |
AC |
1 ms |
256 KB |
1_07.txt |
AC |
1 ms |
256 KB |
1_08.txt |
AC |
1 ms |
256 KB |
1_09.txt |
AC |
1 ms |
256 KB |