// Homura Akemi a.k.a. Starrykiller (/user/235125) // I love Madoka Kaname forever! #include <bits/stdc++.h> using namespace std; auto range(auto l, auto r) { return views::iota(l,r); } auto rev=views::reverse; _GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); } _GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); } #define int long long constexpr int MAXN=1e6+10; int a[MAXN], n; bool okL[MAXN], okR[MAXN]; int deltaL[MAXN], deltaR[MAXN]; void solve() { cin>>n; fill(a+1,a+1+n+1,0); fill(okL+1,okL+1+n+1,0); fill(okR+1,okR+1+n+1,0); fill(deltaL+1,deltaL+1+n+1,0); fill(deltaR+1,deltaR+1+n+1,0); for (int i=1; i<=n; ++i) cin>>a[i]; int cc=0; for (int i=1; i<=n; ++i) cc+=(!a[i-1])&&a[i]; if (cc>1) { cout<<"NIE\n"; return; } int l=1, r=n; while (!a[l]) ++l; while (!a[r]) --r; okL[l-1]=okR[r+1]=1; for (int i=l; i<=r; ++i) { deltaL[i]=a[i]-deltaL[i-1]; okL[i]=okL[i-1]&(deltaL[i]>0); } for (int i=r; i; --i) { deltaR[i]=a[i]-deltaR[i+1]; okR[i]=okR[i+1]&(deltaR[i]>0); } for (int i=l; i<=r; ++i) { int cur=a[i]-deltaL[i-1]-deltaR[i+1]; if (okL[i-1] && okR[i+1] && (cur==0 || cur==1)) { cout<<"TAK\n"; return; } } cout<<"NIE\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin>>T; // int T=1; while (T--) solve(); }
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 | // Homura Akemi a.k.a. Starrykiller (/user/235125) // I love Madoka Kaname forever! #include <bits/stdc++.h> using namespace std; auto range(auto l, auto r) { return views::iota(l,r); } auto rev=views::reverse; _GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); } _GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); } #define int long long constexpr int MAXN=1e6+10; int a[MAXN], n; bool okL[MAXN], okR[MAXN]; int deltaL[MAXN], deltaR[MAXN]; void solve() { cin>>n; fill(a+1,a+1+n+1,0); fill(okL+1,okL+1+n+1,0); fill(okR+1,okR+1+n+1,0); fill(deltaL+1,deltaL+1+n+1,0); fill(deltaR+1,deltaR+1+n+1,0); for (int i=1; i<=n; ++i) cin>>a[i]; int cc=0; for (int i=1; i<=n; ++i) cc+=(!a[i-1])&&a[i]; if (cc>1) { cout<<"NIE\n"; return; } int l=1, r=n; while (!a[l]) ++l; while (!a[r]) --r; okL[l-1]=okR[r+1]=1; for (int i=l; i<=r; ++i) { deltaL[i]=a[i]-deltaL[i-1]; okL[i]=okL[i-1]&(deltaL[i]>0); } for (int i=r; i; --i) { deltaR[i]=a[i]-deltaR[i+1]; okR[i]=okR[i+1]&(deltaR[i]>0); } for (int i=l; i<=r; ++i) { int cur=a[i]-deltaL[i-1]-deltaR[i+1]; if (okL[i-1] && okR[i+1] && (cur==0 || cur==1)) { cout<<"TAK\n"; return; } } cout<<"NIE\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin>>T; // int T=1; while (T--) solve(); } |