Submission #2228946

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream &operator << (ostream& out,const pair<S,T>& o){
    out << "(" << o.first << "," << o.second << ")"; return out;
}
/*
 Atcoder 100~200点代
 アな問題が多いので,まとめる
*/
// https://abc042.contest.atcoder.jp/tasks/abc042_a
//void solve(){ ll A,B,C; cin >> A >> B >> C; if(A == 5 && B == 5 && C == 7){ cout << "YES" << endl; return;} if(A == 5 && B == 7 && C == 5){ cout << "YES" << endl; return;} if(A == 7 && B == 5 && C == 5){ cout << "YES" << endl; return;} cout << "NO" << endl; return ; }
// https://abc043.contest.atcoder.jp/tasks/abc043_a
//void solve(){ ll N; cin >> N; cout << N*(N+1)/2 << endl; }
// https://abc044.contest.atcoder.jp/tasks/abc044_a
//void solve(){ll N,K,X,Y;cin>>N>>K>>X>>Y; cout<<X*min(N,K)+Y*max(0LL,N-K)<<endl;}
// https://abc045.contest.atcoder.jp/tasks/abc045_a
//void solve(){ll a,b,h;cin>>a>>b>>h;cout<<(a+b)*h/2<<endl;}
// https://abc046.contest.atcoder.jp/tasks/abc046_a
//void solve(){ ll a,b,c; cin >> a >> b >> c; set<ll> s; s.insert(a); s.insert(b); s.insert(c); cout << s.size() << endl; }
// https://abc047.contest.atcoder.jp/tasks/abc047_a
//void solve(){ll a,b,c;cin>>a>>b>>c;if(a==b+c||b==a+c||c==a+b)cout<<"Yes"<<endl;else cout<<"No"<<endl;}
// https://abc048.contest.atcoder.jp/tasks/abc048_a
//void solve(){string s1,s2,s3;cin>>s1>>s2>>s3;cout<<"A"<<s2[0]<<"C"<<endl;}
// https://abc049.contest.atcoder.jp/tasks/abc049_a
//void solve(){char c;cin>>c;string s="aiueo";if(s.find(c)!=string::npos)cout<<"vowel"<<endl;else cout<<"consonant"<<endl;}
// https://abc050.contest.atcoder.jp/tasks/abc050_a
//void solve(){ll A,B;char op;cin>>A>>op>>B;if(op=='+')cout<<A+B<<endl;else cout<<A-B<<endl;}
// https://abc051.contest.atcoder.jp/tasks/abc051_a
//void solve(){string s;cin>> s;cout<<s.substr(0,5)<<" "<<s.substr(6,7)<<" "<<s.substr(14)<<endl;}
// https://abc052.contest.atcoder.jp/tasks/abc052_a
//void solve(){ll A,B,C,D;cin>>A>>B>>C>>D;cout<<max(A*B,C*D)<<endl;}
// https://abc053.contest.atcoder.jp/tasks/abc053_a
//void solve(){ll x;cin>>x;cout<<(x<1200?"ABC":"ARC")<<endl;}
// https://abc054.contest.atcoder.jp/tasks/abc054_a
//void solve(){ll A,B;cin>>A>>B;if(A==1)A=14;if(B==1)B=14;cout<<(A>B?"Alice":(A==B?"Draw":"Bob"))<<endl;}
// https://abc055.contest.atcoder.jp/tasks/abc055_a
//void solve(){ll N;cin>>N;cout<<800*N-200*(N/15)<<endl;}
// https://abc056.contest.atcoder.jp/tasks/abc056_a
//void solve(){char a,b;cin>>a>>b;if(a=='H')cout<<b<<endl;else if(b=='H')cout<<'D'<<endl;else cout<<'H'<<endl;}
// https://abc057.contest.atcoder.jp/tasks/abc057_a
//void solve(){ll A,B;cin>>A>>B;cout<<(A+B)%24<<endl;}
// https://abc058.contest.atcoder.jp/tasks/abc058_a
//void solve(){ll a,b,c;cin>>a>>b>>c;cout<<(b-a==c-b?"YES":"NO")<<endl;}
// https://abc059.contest.atcoder.jp/tasks/abc059_a
//void solve(){string s1,s2,s3;cin>>s1>>s2>>s3;cout<<(char)toupper(s1[0])<<(char)toupper(s2[0])<<(char)toupper(s3[0])<<endl;}
// https://abc060.contest.atcoder.jp/tasks/abc060_a
//void solve(){string A,B,C;cin>>A>>B>>C;cout<<(A[A.length()-1]==B[0]&&B[B.length()-1]==C[0]?"YES":"NO")<<endl;}
// https://abc061.contest.atcoder.jp/tasks/abc061_a
//void solve(){ll A,B,C;cin>>A>>B>>C;cout<<(C>=A&&C<=B?"Yes":"No")<<endl;}
// https://abc062.contest.atcoder.jp/tasks/abc062_a
//void solve(){ll x,y;cin>>x>>y;vector<vector<ll>> g={{1,3,5,7,8,10,12},{4,6,9,11},{2}}; ll gx,gy; for(int i=0;i<3;i++)for(auto v:g[i]){if(v==x) gx=i;if(v==y)gy=i;}cout<<(gx==gy?"Yes":"No")<<endl;}
// https://abc063.contest.atcoder.jp/tasks/abc063_a
//void solve(){ll A,B;cin>>A>>B;cout<<(A+B>=10?"error":to_string(A+B))<<endl;}
// https://abc064.contest.atcoder.jp/tasks/abc064_a
//void solve(){ll r,g,b;cin>>r>>g>>b;cout<<((100*r+10*g+b)%4==0?"YES":"NO")<<endl;}
// https://abc065.contest.atcoder.jp/tasks/abc065_a
//void solve(){ll X,A,B;cin>>X>>A>>B;cout<<(A>=B?"delicious":(X+A>=B?"safe":"dangerous"))<<endl;}
// https://abc066.contest.atcoder.jp/tasks/abc066_a
//void solve(){ll a,b,c;cin>>a>>b>>c;cout<<min({a+b,b+c,c+a})<<endl;}
// https://abc067.contest.atcoder.jp/tasks/abc067_a
//void solve(){ll A,B;cin>>A>>B;cout<<(A%3==0||B%3==0||(A+B)%3==0?"Possible":"Impossible")<<endl;}
// https://abc068.contest.atcoder.jp/tasks/abc068_a
//void solve(){ll N;cin>>N;cout<<"ABC"<<N<<endl;}
// https://abc069.contest.atcoder.jp/tasks/abc069_a
//void solve(){ll n,m;cin>>n>>m;cout<<(n-1)*(m-1)<<endl;}
// https://abc070.contest.atcoder.jp/tasks/abc070_a
//void solve(){ll N;cin>>N;cout<<(to_string(N)[0]==to_string(N)[2]?"Yes":"No")<<endl;}
// https://abc071.contest.atcoder.jp/tasks/abc071_a
//void solve(){ll x,a,b;cin>>x>>a>>b;cout<<(abs(x-a)<abs(x-b)?"A":"B")<<endl;}
// https://abc072.contest.atcoder.jp/tasks/abc072_a
//void solve(){ll X,t;cin>>X>>t;cout<<max(0LL,X-t)<<endl;}
// https://abc073.contest.atcoder.jp/tasks/abc073_a
//void solve(){ll N;cin>>N;cout<<(to_string(N).find('9')!=string::npos?"Yes":"No")<<endl;}
// https://abc074.contest.atcoder.jp/tasks/abc074_a
//void solve(){ll N,A;cin>>N>>A;cout<<N*N-A<<endl;}
// https://abc075.contest.atcoder.jp/tasks/abc075_a
//void solve(){ll A,B,C;cin>>A>>B>>C;cout<<(A==B?C:(B==C)?A:B)<<endl;}
// https://abc076.contest.atcoder.jp/tasks/abc076_a
//void solve(){ll R,G;cin>>R>>G;cout<<2*G-R<<endl;}
// https://abc077.contest.atcoder.jp/tasks/abc077_a
//void solve(){char C[2][3];for(int i=0;i<2;i++)for(int j=0;j<3;j++)cin>>C[i][j];for(int i=0;i<3;i++)if(C[0][i]!=C[1][2-i]){cout<<"NO"<<endl;return;}cout<<"YES"<<endl;}
// https://abc078.contest.atcoder.jp/tasks/abc078_a
//void solve(){string A,B;cin>>A>>B;ll a=stoi(A,nullptr,16),b=stoi(B,nullptr,16); cout<<(a>b?">":(a==b?"=":"<"))<<endl;}
// https://abc079.contest.atcoder.jp/tasks/abc079_a
//void solve(){ll N;cin>>N;string S=to_string(N);cout<<((S[0]==S[1]&&S[1]==S[2]&&S[2]==S[0])||(S[1]==S[2]&&S[2]==S[3]&&S[3]==S[1])?"Yes":"No")<<endl;}
// https://abc080.contest.atcoder.jp/tasks/abc080_a
//void solve(){ll N,A,B;cin>>N>>A>>B;cout<<min(A*N,B)<<endl;}
// https://abc081.contest.atcoder.jp/tasks/abc081_a
//void solve(){string s;cin>>s;int ans=0;for(auto c:s)if(c=='1')ans++;cout<<ans<<endl;}
// https://abc082.contest.atcoder.jp/tasks/abc082_a
//void solve(){ll a,b;cin>>a>>b;cout<<int((double)(a+b)/2.0 + 0.5)<<endl;}
// https://abc083.contest.atcoder.jp/tasks/abc083_a
//void solve(){ll A,B,C,D;cin>>A>>B>>C>>D;ll L=A+B,R=C+D;cout<<(L>R?"Left":(L==R)?"Balanced":"Right")<<endl;}
// https://abc084.contest.atcoder.jp/tasks/abc084_a
//void solve(){ll M;cin>>M;cout<<48-M<<endl;}
// https://abc085.contest.atcoder.jp/tasks/abc085_a
//void solve(){string S;cin>>S;S[3]='8';cout<<S<<endl;}
// https://abc086.contest.atcoder.jp/tasks/abc086_a
//void solve(){ll a,b;cin>>a>>b;cout<<(a*b&1?"Odd":"Even")<<endl;}
// https://abc087.contest.atcoder.jp/tasks/abc087_a
//void solve(){ll X,A,B;cin>>X>>A>>B;cout<<(X-A)-(X-A)/B*B<<endl;}
// https://abc088.contest.atcoder.jp/tasks/abc088_a
//void solve(){ll N,A;cin>>N>>A;cout<<(N%500<=A?"Yes":"No")<<endl;}
// https://abc089.contest.atcoder.jp/tasks/abc089_a
//void solve(){ll N;cin>>N;cout<<N/3<<endl;}
// https://abc090.contest.atcoder.jp/tasks/abc090_a
//void solve(){char c[3][3];for(int i = 0;i<3;i++)for(int j = 0;j<3;j++)cin>>c[i][j];cout<<c[0][0]<<c[1][1]<<c[2][2]<<endl;}
// https://abc091.contest.atcoder.jp/tasks/abc091_a
//void solve(){ll A,B,C;cin>>A>>B>>C;cout<<(A+B>=C?"Yes":"No")<<endl;}
// https://apc001.contest.atcoder.jp/tasks/apc001_a
//void solve(){ll X,Y;cin>>X>>Y;cout<<(X%Y==0?-1:X*(Y-1))<<endl;}
// https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_a
//void solve(){ll H,W;cin>>H>>W;string S;for(int i = 0; i < H;i++)for(int j = 0; j < W;j++){cin>>S;if(S=="snuke")cout<<(char)('A'+j)<<i+1<<endl;}}
// https://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_a
//void solve(){string s;cin>>s;cout<<s.substr(0,4)<<" "<<s.substr(4)<<endl;}
// https://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_a
//void solve(){string S;cin>>S;string s="CODEFESTIVAL2016";int ans = 0;for(int i=0;i<16;i++)if(S[i]!=s[i])ans++;cout<<ans<<endl;}
// https://code-festival-2016-qualc.contest.atcoder.jp/tasks/codefestival_2016_qualC_a
//void solve(){string s;cin>>s;bool f=false;for(int i = 0; i < s.length();i++) if(!f){if(s[i]=='C')f=true;}else{if(s[i]=='F'){cout<<"Yes"<<endl;return;}}cout<<"No"<<endl;}
// https://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_a
//void solve(){string S;cin>>S;cout<<(S.substr(0,4)=="YAKI"?"Yes":"No")<<endl;}
// https://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_a
//void solve(){string S;cin>>S;cout<<S.substr(0,S.length()-8)<<endl;}
// https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_a
//void solve(){string S;cin>>S;for(int i = 0;i<S.length()-1;i++)if(S[i]=='A'&&S[i+1]=='C'){cout<< "Yes"<<endl; return;}cout<<"No"<<endl;}
// https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_a
//void solve(){ll t[8];for(int i = 0; i < 8;i++) cin >> t[i];cout<<*max_element(t,t+8)<<endl;}
// https://colopl2018-qual.contest.atcoder.jp/tasks/colopl2018_qual_a
//void solve(){ll A,B;cin>>A>>B;string S;cin>>S;cout<<(A<=S.length()&&S.length()<=B?"YES":"NO")<<endl;}
// https://ddcc2016-qual.contest.atcoder.jp/tasks/ddcc_2016_qual_a
//void solve(){double A,B,C;cin>>A>>B>>C;cout<<fixed<<setprecision(12)<<(B/A)*C<<endl;}
// https://ddcc2017-qual.contest.atcoder.jp/tasks/ddcc2017_qual_a
//void solve(){string S;cin>>S;cout<<(S[0]==S[1]&&S[1]!=S[2]&&S[2]==S[3]?"Yes":"No")<<endl;}
// https://soundhound2018.contest.atcoder.jp/tasks/soundhound2018_a
//void solve(){string X,Y;cin>>X>>Y;cout<<(X[0]=='S'&&Y[0]=='H'?"YES":"NO")<<endl;}
// https://tenka1-2017-beginner.contest.atcoder.jp/tasks/tenka1_2017_a
//void solve(){string S;cin>>S;int ans=0;for(int i=0;i<6;i++)if(S[i]=='1')ans++;cout<<ans<<endl;}
// https://yahoo-procon2018-qual.contest.atcoder.jp/tasks/yahoo_procon2018_qual_a
//void solve(){string S;cin>>S;cout<<(S.substr(0,3)=="yah"&&S[3]==S[4]?"YES":"NO")<<endl;}
// https://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_a
//void solve(){string S,yahoo="yahoo";cin>>S;vector<int> a(5);iota(a.begin(),a.end(),0);do{string s;for(int i = 0; i < 5;i++)s+=yahoo[a[i]];if(s==S){cout << "YES"<<endl;return;}}while(next_permutation(a.begin(),a.end()));cout<<"NO"<<endl;}
// https://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_a
//void solve(){ll ans=0;for(int i=1;i<=100;i++)if(i%3!=0&&i%5!=0)ans+=i;cout<<ans<<endl;}
// https://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_a
//void solve(){int n=3,ans=20;;while(n--){ans=(ans*ans+4)/8;}cout<<ans<<endl;}
// https://dwacon2017-prelims.contest.atcoder.jp/tasks/dwango2017qual_a
//void solve(){ll n,a,b;cin>>n>>a>>b;cout<<max(0LL,a+b-n)<<endl;}
// https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_a
//void solve(){string s;cin>>s;cout<<(s[0]==s[2]&&s[1]==s[3]?"Yes":"No")<<endl;}

// ========================== ここから　200 =================================//
// https://abc042.contest.atcoder.jp/tasks/abc042_b
//void solve(){ll N,L;cin>>N>>L;vector<string>S(N);for(auto&in:S)cin>>in;sort(S.begin(),S.end());for(auto s:S)cout<<s;cout<<endl;}
// https://abc043.contest.atcoder.jp/tasks/abc043_b
//void solve(){string s;cin>>s;stack<char> st;for(auto c:s)if(c=='B'){if(st.size()!=0)st.pop();}else st.push(c);string ans;while(st.size()){ans+=st.top();st.pop();}reverse(ans.begin(),ans.end());cout<<ans<<endl;}
// https://abc044.contest.atcoder.jp/tasks/abc044_b
//void solve(){string w;cin>>w;map<char,int> mp;for(auto c:w)mp[c]++;for(auto v:mp)if(v.second&1){cout<<"No"<<endl;return;}cout<<"Yes"<<endl;}
// https://abc045.contest.atcoder.jp/tasks/abc045_b
//void solve(){string S[3];int c[3]={};int at=0; cin>>S[0]>>S[1]>>S[2];do{if(c[at]==S[at].length()){if(at == 0){cout<<"A";}else if(at == 1){ cout << "B"; }else { cout << "C";}cout << endl; return;}char s = S[at][c[at]];if (s == 'a'){c[at]++;at = 0;}else if(s == 'b'){c[at]++;at = 1;}else if(s == 'c'){c[at]++;at = 2;}} while (1);}
// https://abc046.contest.atcoder.jp/tasks/abc046_b
//void solve(){ll N,K;cin>>N>>K;cout<<fixed<<K*(ll)pow(K-1,N-1)<<endl;}
// https://abc047.contest.atcoder.jp/tasks/abc047_b
//void solve(){ int W, H, N; cin >> W >> H >> N; vector<vector<int>>v(H+1,vector<int>(W+1));
//    for (int i = 0; i < N;i++){int x, y, a; cin >> x >> y >> a;
//        if (a == 1) for (int j = 1; j <= x;j++)for (int k = 1; k <= H;k++)v[k][j] = true;
//        if (a == 2) for (int j = x + 1; j <= W;j++)for (int k = 1; k <= H;k++) v[k][j] = true;
//        if (a == 3) for (int j = 1; j <= y;j++) for (int k = 1; k <= W;k++) v[j][k] = true;
//        if (a == 4) for (int j = y + 1; j <= H;j++) for (int k = 1; k <= W;k++) v[j][k] = true;
//    }
//    int Ans = 0; for (int i = 1; i <= H;i++)for (int j = 1; j <= W;j++)if(!v[i][j])Ans++; cout << Ans << endl;
//}
// https://abc048.contest.atcoder.jp/tasks/abc048_b
//void solve(){ll a,b,x;cin>>a>>b>>x; if(a==0)cout<<b/x+1<<endl;else cout<<b/x-(a-1)/x<<endl;}
// https://abc049.contest.atcoder.jp/tasks/abc049_b
//void solve(){ll H,W;cin>>H>>W;vector<string> S(H);for(auto&in:S)cin>>in;for(auto s:S)cout<<s<<endl<<s<<endl;}
// https://abc050.contest.atcoder.jp/tasks/abc050_b
//void solve(){ll N;cin>>N;vector<ll>T(N);for(auto&in:T)cin>>in;ll sum=accumulate(T.begin(),T.end(),0LL);ll M;cin>>M;for(int i = 0; i < M;i++){ll P,X;cin>>P>>X;cout<<sum-T[P-1]+X<<endl;}}
// https://abc051.contest.atcoder.jp/tasks/abc051_b
//void solve(){ll K,S;cin>>K>>S;int ans=0;for(int x=0;x<=K;x++)for(int y=0;y<=K;y++)if(S-x-y>=0&&S-x-y<=K)ans++;cout<<ans<<endl;}
// https://abc052.contest.atcoder.jp/tasks/abc052_b
//void solve(){ll N;string S;cin>>N>>S;int x=0,ans=0;for(auto c:S)if(c=='I')ans=max(ans,++x); else x--;cout<<ans<<endl;}
// https://abc053.contest.atcoder.jp/tasks/abc053_b
//void solve(){string s;cin>>s;cout<<s.rfind('Z')-s.find('A')+1<<endl;}
// https://abc054.contest.atcoder.jp/tasks/abc054_b
//void solve(){ll N,M;cin>>N>>M;vector<string> S(N+M);for(auto&in:S)cin>>in;for(int i=0;i<=N-M;i++)for(int j=0;j<=N-M;j++){auto f=[&]{for(int k=0;k<M;k++)if(S[i+k].substr(j,M)!=S[N+k])return false;return true;}();if(f){cout<<"Yes"<<endl;return;}}cout<<"No"<<endl;}
// https://abc055.contest.atcoder.jp/tasks/abc055_b
//void solve(){ll N;cin>>N;ll MOD=1e9+7;ll fact=1;for(ll i=1;i<=N;i++)fact=fact*i%MOD;cout<<fact<<endl;}
// https://abc056.contest.atcoder.jp/tasks/abc056_b
//void solve(){ll W,a,b;cin>>W>>a>>b;cout<<max(0LL,max(a,b)-min(a,b)-W)<<endl;}
// https://abc057.contest.atcoder.jp/tasks/abc057_b
//void solve(){ll N,M;cin>>N>>M;vector<ll>a(N),b(N),c(M),d(M);vector<vector<ll>>dist(N,vector<ll>(M));for(int i=0;i<N;i++)cin>>a[i]>>b[i];for(int i=0;i<M;i++)cin>>c[i]>>d[i];for(int i=0;i<N;i++)for(int j=0;j<M;j++)dist[i][j]=abs(a[i]-c[j])+abs(b[i]-d[j]);for(int i=0;i<N;i++)cout<<min_element(dist[i].begin(),dist[i].end())-dist[i].begin()+1<<endl;}
// https://abc058.contest.atcoder.jp/tasks/abc058_b
//void solve(){string O,E;cin>>O>>E;for(int i=0;i<O.length();i++){cout<<O[i];if(i<E.length())cout<<E[i];}cout<<endl;}
// https://abc059.contest.atcoder.jp/tasks/abc059_b
//void solve(){string A,B;cin>>A>>B;cout<<(A.length()>B.length()?"GREATER":(A.length()<B.length()?"LESS":(A>B?"GREATER":(A<B?"LESS":"EQUAL"))))<<endl;}
// https://abc060.contest.atcoder.jp/tasks/abc060_b
//void solve(){ll A,B,C;cin>>A>>B>>C;for(int i=0;i<1000;i++)if((B*i+C)%A==0){cout<<"YES"<<endl;return;}cout<<"NO"<<endl;}
// https://abc061.contest.atcoder.jp/tasks/abc061_b
//void solve(){ll N,M;cin>>N>>M;ll a,b;vector<ll> c(N);for(int i=0;i<M;i++){cin>>a>>b;c[a-1]++;c[b-1]++;}for(auto v:c)cout<<v<<endl;}
// https://abc062.contest.atcoder.jp/tasks/abc062_b
//void solve(){ll H,W;cin>>H>>W;vector<string>a(H);for(auto&in:a)cin>>in;cout<<string(W+2,'#')<<endl;for(auto s:a)cout<<"#"<<s<<"#"<<endl;cout<<string(W+2,'#')<<endl;}
// https://abc063.contest.atcoder.jp/tasks/abc063_b
//void solve(){string S;cin>>S;sort(S.begin(),S.end());ll l=S.length();S.erase(unique(S.begin(),S.end()),S.end());cout<<(l==S.length()?"yes":"no")<<endl;}
// https://abc064.contest.atcoder.jp/tasks/abc064_b
//void solve(){ll N;cin>>N;vector<ll>a(N);for(auto&in:a)cin>>in;cout<<*max_element(a.begin(),a.end())-*min_element(a.begin(),a.end())<<endl;}
// https://abc065.contest.atcoder.jp/tasks/abc065_b
void solve(){ll N;cin>>N;vector<ll>a(N);for(auto&in:a)cin>>in;int n=1;for(int i=0;i<=N;i++){n=a[n-1];if(n==2){cout<<i+1<<endl;return;}}cout<<-1<<endl;}


// Main function
int main(void) {cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; }

Submission Info

Judge Result