-
Notifications
You must be signed in to change notification settings - Fork 2
/
1354B.cpp
130 lines (120 loc) · 4.32 KB
/
1354B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Author : Mars_Coder
// https://codeforces.com/problemset/problem/1354/B
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
#define ln "\n" // no flush, oppos of endl
#define _flush endl
#define stop_sync ios::sync_with_stdio(false) // not to use c-style io
#define untie_ios cin.tie(nullptr) // no flush
#define lli long long int
#define vi vector<int>
#define vii vector<lli>
#define vch vector<char>
#define double long double
#define vss vector<string>
#define vpp(T1, T2) vector<pair<T1, T2>>
#define pq priority_queue // high prec.
#define pqq(T) priority_queue<T, vector<T>, greater<T>>
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define Fi(p) get<0>(p)
#define Sc(p) get<1>(p)
#define sz(x) int ((x).size())
#define all(x) (x).begin(), (x).end()
#define scanv(x) for(auto &i: x) cin >> i
#define bin_sc(a, x) binary_search(all(a), x)
#define lbd(a, x) lower_bound(all(a), x) // an iter.
#define ubd(a, x) upper_bound(all(a), x) // an iter.
#define eq_seg(a, x) equal_range(all(a), x) // a pair of lb, ub
#define minE(a) (*min_element(all(a)))
#define maxE(a) (*max_element(all(a)))
#define FIXED(x) cout << fixed << setprecision(x)
#define mem(a, v) memset(a, v, sizeof a) // 0,-1 for int, and all char
#define filla(a, n, v) fill(a, a + n, v) // for arr.
#define fillv(a, v) fill(all(a), v) // for vec.
#define _fillv(a, n, v) fill_n(a.begin(), n, v)
#define glue(x, y) x##y
#define feed(x) cout << x << ln
#define feeds(x) cout << x << ' '
#define print(x) cout << (#x) << ": " << (x) << ln
#define printv(v) for(auto i: v) cout << i << ' '; cout << ln
#define printvv(v) for(auto i: v) {for(auto j: i) cout << j << ' '; cout << ln;}
#define printm(m) for(auto i: m) cout << Fi(i) << " -> " << Sc(i) << ln
#define prints(s) for(auto i: s) cout << i << ' '; cout << ln
#define uceil(a, b) ((a + b - 1) / (b))
#define gcd(a, b) __gcd(a, b)
const string yms[]{"YES", "Yes", "yes"};
const string nms[]{"NO", "No", "no"};
const double PI = acos(-1.0L);
struct{const int i = (1e9) + 7; const lli l = (lli)(1e9) + 7ll;}MOD;
struct{const int i = INT_MAX; const lli l = LLONG_MAX;}inf;
template<typename type> type Nsum(type n){return (n * (n + 1)) / (type)2;}
template<typename type> type uround(type a, type b) {return (((a) * 1.0000) / (b) + 0.500000);}
template<typename type> type pow2(type p){return ((type) 1) << p;}
// nxt templ.
// array<T, n> a = {}
int main(void){
stop_sync;
untie_ios;
#ifndef ONLINE_JUDGE
//freopen("generator.txt", "r", stdin);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int t(1);
cin >> t;
while(t--){
string s;
cin >> s;
vi ones, twos, threes;
for(int i = 0; i < sz(s); ++i){
if(s[i] == '1') ones.pb(i);
else if(s[i] == '2') twos.pb(i);
else threes.pb(i);
}
if(sz(ones) == 0 || sz(twos) == 0 || sz(threes) == 0) feed(0);
else{
int mn = inf.i;
for(int i = 0; i < sz(s); ++i){
array<int, 3> l = {inf.i, inf.i, inf.i};
if(s[i] == '1'){
l[0] = i;
if(lbd(twos, i) != twos.end()) l[1] = *lbd(twos, i);
if(lbd(threes, i) != threes.end()) l[2] = *lbd(threes, i);
sort(all(l));
mn = min(mn, l[2] - l[0] + 1);
}else if(s[i] == '2'){
l[0] = i;
if(lbd(ones, i) != ones.end()) l[1] = *lbd(ones, i);
if(lbd(threes, i) != threes.end()) l[2] = *lbd(threes, i);
sort(all(l));
mn = min(mn, l[2] - l[0] + 1);
}else{
l[0] = i;
if(lbd(ones, i) != ones.end()) l[1] = *lbd(ones, i);
if(lbd(twos, i) != twos.end()) l[2] = *lbd(twos, i);
sort(all(l));
mn = min(mn, l[2] - l[0] + 1);
}
}
feed(mn);
}
}
return 0;
}
/*
some familiar issues & sugg.:
!----> [RE-READ THE CODE!]
!----> [invariants to array?]
!----> [look at global variables and their values]
!----> [llabs() for long long int type]
!----> [look at input size and time limit]
!----> [No sync with puts fn]
!----> [prefix vs suffix]
!----> [binary search? -> ubd, lbd]
!----> [array contains duplicate values!]
!----> [(a/b+1)*b vs uceil(a,b)*b]
*/