Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial is loading...

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    cout<<s;
    reverse(s.begin(),s.end());
    cout<<s;
    return 0;
}

Tutorial is loading...

Code

#include "bits/stdc++.h"

#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a)		cerr<<#a<<" : "<<a<<endl
#else
#define tr(a)    
#endif

#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)	for(int i=a;i<b;i++)
using namespace std;

int x[10][1000005];

int f(int x){
	if(x<10)return x;
	int prod=1;
	while(x){
		if(x%10)prod*=(x%10);
		x/=10;
	}
	return f(prod);
}

void solve(){
	for(int i=1;i<=1000000;i++){
		x[f(i)][i]++;
	}
	for(int i=1;i<10;i++){
		for(int j=1;j<=1000000;j++){
			x[i][j]+=x[i][j-1];
		}
	}
	int Q;
	cin>>Q;
	while(Q--){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<x[k][r]-x[k][l-1]<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Tutorial is loading...

Code

#include "bits/stdc++.h"

#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)	for(int i=a;i<b;i++)
using namespace std;

void solve(){
	int n,a,b;
	cin>>n>>a>>b;
	vector<int>v(n);
	iota(all(v),1);
	int i=0;
	while(i<n){
		if((n-i)%b==0){
			if(b>1)rotate(v.begin()+i,v.begin()+i+1,v.begin()+i+b);
			i+=b;
		}
		else{
			if(i+a>n){
				cout<<-1;
				return;
			}
			if(a>1)rotate(v.begin()+i,v.begin()+i+1,v.begin()+i+a);
			i+=a;
		}
	}
	for(auto j:v)cout<<j<<" ";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Tutorial is loading...

Thanks to radoslav11 for nice and short editorial in comments.

Code

#include "bits/stdc++.h"

#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a)		cerr<<#a<<" : "<<a<<endl
#else
#define tr(a)    
#endif
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)	for(int i=a;i<b;i++)
using namespace std;

int par[20][400000];
ll par_sum[20][400000];
int w[400000];

void solve(){
	int Q;
	cin>>Q;
	w[0]=INT_MAX;
	int last=0;
	int cur=1;
	for(int i=0;i<20;i++)par_sum[i][1]=1e16;
	while(Q--){
		int ch;
		cin>>ch;
		if(ch==1){
			ll p,q;
			cin>>p>>q;
			p^=last;
			q^=last;
			cur++;
			w[cur]=q;
			if(w[p]>=w[cur]){
				par[0][cur]=p;
			}
			else{
				int from=p;
				for(int i=19;i>=0;i--){
					if(w[par[i][from]]<w[cur])
						from=par[i][from];
				}
				par[0][cur]=par[0][from];
			}
			par_sum[0][cur]=(par[0][cur]==0?1e16:w[par[0][cur]]);
			for(int i=1;i<20;i++){
				par[i][cur]=par[i-1][par[i-1][cur]];
				par_sum[i][cur]=(par[i][cur]==0?1e16:par_sum[i-1][cur]+par_sum[i-1][par[i-1][cur]]);
			}
		}
		else{
			ll p,q;
			cin>>p>>q;
			p^=last;
			q^=last;
			if(w[p]>q){
				cout<<0<<endl;
				last=0;
			}
			else{
				q-=w[p];
				int ans=1;
				for(int i=19;i>=0;i--){
					if(par_sum[i][p]<=q){
						ans+=(1<<i);
						q-=par_sum[i][p];
						p=par[i][p];
					}
				}
				cout<<ans<<endl;
				last=ans;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Tutorial is loading...

Code

#include "bits/stdc++.h"

#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)	for(int i=a;i<b;i++)
using namespace std;

int dp[5001][5001];
ll expo(ll base, ll exponent, ll mod) {
    ll ans = 1;
    while(exponent !=0 ) {
        if((exponent&1) == 1) {
            ans = ans*base ;
            ans = ans%mod;
        }
        base = base*base;
        base %= mod;
        exponent>>= 1;
    }
    return ans%mod;
}
int fill(int diffs,int a,int tot){
	if(dp[diffs][a]>=0)return dp[diffs][a];
	int b=tot-a;
	if(diffs==0){
		return dp[diffs][a]=expo(2,b,hell);
	}
	return dp[diffs][a]=((b?1LL*b*fill(diffs-1,a+1,tot):0LL)+(a?1LL*a*fill(diffs-1,a,tot):0LL))%hell;
}

void solve(){
	int N,k;
	cin>>N>>k;
	memset(dp,-1,sizeof dp);
	cout<<fill(k,0,N)<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Tutorial is loading...

Code

#include "bits/stdc++.h"


#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)    for(int i=a;i<b;i++)
using namespace std;

bool Q;
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const {
        return Q ? p < o.p : k < o.k;
    }
};
struct LineContainer : multiset<Line> {
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b){
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
        return l.k * x + l.m;
    }
};

vector<int> x,y;
vector<vi> adj;
vector<ll> ans;
vector<int> subsize;
void dfs1(int u,int v){
    subsize[u]=1;
    for(auto i:adj[u]){
        if(i==v)continue;
        dfs1(i,u);
        subsize[u]+=subsize[i];
    }
}

void dfs2(int v, int p,LineContainer& cur){
    int mx=-1,bigChild=-1;
    bool leaf=1;
    for(auto u:adj[v]){
        if(u!=p and subsize[u]>mx){
            mx=subsize[u];
            bigChild=u;
            leaf=0;
        }
    }
    if(bigChild!=-1){
        dfs2(bigChild,v,cur);
    }
    for(auto u:adj[v]){
        if(u!=p and u!=bigChild){
            LineContainer temp;
            dfs2(u,v,temp);
            for(auto i:temp){
                cur.add(i.k,i.m);
            }
        }
    }
    if(!leaf)ans[v]=-cur.query(x[v]);
    else ans[v]=0;
    cur.add(-y[v],-ans[v]);
}
void solve(){
    int n;
    cin>>n;
    x.resize(n+1);
    y.resize(n+1);
    ans.resize(n+1);
    subsize.resize(n+1);
    adj.resize(n+1);
    rep(i,1,n+1)cin>>x[i];
    rep(i,1,n+1)cin>>y[i];
    rep(i,1,n){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs1(1,0);
    LineContainer lc;
    dfs2(1,0,lc);
    rep(i,1,n+1)cout<<ans[i]<<" ";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Tutorial is loading...

Code 1

#include <bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
using namespace std;
const int MAXN=1000005;
string s;
struct PalindromicTree{
    int N,cur;
    vector<map<int,int>> next;
    vector<int> link,start,len,diff,slink;
    PalindromicTree(): N(0),cur(0){
        node();
        len[0]=-1;
        node();
    }
    int node(){
        next.emplace_back();
        link.emplace_back(0);
        start.emplace_back(0);
        len.emplace_back(0);
        diff.emplace_back(0);
        slink.emplace_back(0);
        return N++;
    }
    void add_letter(int idx){
        while(true){
            if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx])
                break;
            cur=link[cur];
        }
        if(next[cur].find(s[idx])!=next[cur].end()){
            cur=next[cur][s[idx]];
            return;
        }
        node();
        next[cur][s[idx]]=N-1;
        len[N-1]=len[cur]+2;
        start[N-1]=idx-len[N-1]+1;
        if(len[N-1]==1){
            link[N-1]=diff[N-1]=slink[N-1]=1;
            cur=N-1;
            return;
        }
        while(true){
            cur=link[cur];
            if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx])
                break;
        }
        link[N-1]=next[cur][s[idx]];
        diff[N-1]=len[N-1]-len[link[N-1]];
        if(diff[N-1]==diff[link[N-1]])
        	slink[N-1]=slink[link[N-1]];
        else
        	slink[N-1]=link[N-1];
        cur=N-1;
    }
};
ll dp[MAXN],sans[MAXN];
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	PalindromicTree pt;
	int i,cur;
	string str;
	cin>>str;
	for(i=0;i<sz(str)/2;i++){
		s.pb(str[i]);
		s.pb(str[sz(str)-i-1]);
	}
	dp[0]=1;
	for(i=1;i<=sz(s);i++){
		pt.add_letter(i-1);
		for(cur=pt.cur;cur>1;cur=pt.slink[cur]){
			sans[cur]=dp[i-pt.len[pt.slink[cur]]-pt.diff[cur]];
			if(pt.diff[cur]==pt.diff[pt.link[cur]])
				sans[cur]=(sans[cur]+sans[pt.link[cur]])%hell;
			dp[i]=(dp[i]+sans[cur])%hell;
		}
		if(i&1)
			dp[i]=0;
	}
	cout<<dp[sz(s)];
	return 0;
}

Code 2

#define NDEBUG
NDEBUG


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <queue>
#include <random>


#define forn(t, i, n) for (t i = 0; i < (n); ++i)


using namespace std;

// TC_REMOVE_BEGIN
/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);
// TC_REMOVE_END


// Section with adoption of array and vector algorithms.


#define ENABLE_IF(e) typename enable_if<e>::type* = nullptr

namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    template<int N>
    struct bytetype {
        
    };

    template<>
    struct bytetype<4> {
        typedef uint32_t type;
    };

    
    template<>
    struct bytetype<1> {
        typedef uint8_t type;
    };

    
    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}


/*
TODOs:
 primitive root
 discrete log

 tests!!!
*/

namespace mod_impl {
    /// caide keep
    template <class T>
    constexpr inline T mod(T MOD) {
        return MOD;
    }

    /// caide keep
    template <class T>
    constexpr inline T mod(T* MOD) {
        return *MOD;
    }

    /// caide keep
    template <class T>
    constexpr inline T max_mod(T MOD) {
        return MOD - 1;
    }

    /// caide keep
    template <class T>
    constexpr inline T max_mod(T*) {
        return numeric_limits<T>::max() - 1;
    }

    
    constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) {
        return a > ~b ? 0 : a + b;
    }

    
    /// caide keep
    template <class T>
    constexpr inline uint64_t next_divisible(T mod, uint64_t max) {
        return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod);
    }

    /// caide keep
    template <class T>
    constexpr inline uint64_t next_divisible(T*, uint64_t) {
        return 0;
    }

    //caide keep
    constexpr int IF_THRESHOLD = 2;

    template <class T, T MOD_VALUE, uint64_t MAX,
            class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
            ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        return value;
    }

    template <class T, T MOD_VALUE, uint64_t MAX,
            class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
            ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        while (value >= mod(MOD_VALUE)) {
            value -= mod(MOD_VALUE);
        }
        return (RET)value;
    }

    
}


#define MAX_MOD mod_impl::max_mod(MOD_VALUE)

struct DenormTag {};

template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)>
struct ModVal {
    typedef typename template_util::minimal_uint<MAX>::type storage;
    storage value;

    /// caide keep
    inline ModVal(): value(0) {
        assert(MOD >= 2);
    }

    
    inline ModVal(storage v, DenormTag): value(v) {
        assert(MOD >= 2);
        assert(v <= MAX);
    };

    inline operator ModVal<T, MOD_VALUE>() {
        return {v(), DenormTag()};
    };

    
    typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const {
        return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value);
    }
};


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2),
        ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX>
inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
    lhs = lhs + rhs;
    return lhs;
}


template <class T, T MOD_VALUE, class MOD_TYPE>
struct ModCompanion {
    typedef MOD_TYPE mod_type;
    typedef ModVal<mod_type, MOD_VALUE> type;
    

    template <uint64_t C>
    inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() {
        return {C, DenormTag()};
    };

    
};


#undef MAX_MOD

template <uint64_t MOD_VALUE>
struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> {
    template<uint64_t VAL>
    static constexpr uint64_t literal_builder() {
        return VAL;
    }

    template<uint64_t VAL, char DIGIT, char... REST>
    static constexpr uint64_t literal_builder() {
        return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>();
    }
};


#define REGISTER_MOD_LITERAL(mod, suffix) \
template <char... DIGITS> mod::type operator "" _##suffix() { \
    return mod::c<mod::literal_builder<0, DIGITS...>()>(); \
}


template <class T, T MOD_VALUE, uint64_t MAX>
inline ostream& operator<<(ostream& s, ModVal<T, MOD_VALUE, MAX> val) {
    s << val.v();
    return s;
}

using md = Mod<1000000007>;
using mt = md::type;
REGISTER_MOD_LITERAL(md, mod)

struct Triple {
    int start, delta, count;

    int end() {
        return start + delta * (count - 1);
    }
};

// ostream& operator<<(ostream& out, const Triple& t) {
//     out << "(" << t.start << ", " << t.delta << ", " << t.count << ")";
//     return out;
// }

void solve(istream& in, ostream& out) {
    auto s = next<string>(in);
    string s1;
    s1.reserve(2 * s.length());
    forn (int, i, s.length() / 2) {
        s1.push_back(s[i]);
        s1.push_back(s[s.length() - i - 1]);
    }
    int n = s1.length();
    vector<Triple> g;
    vector<mt> d(n + 1), cache(n + 1);
    d[0] = 1_mod;
    forn (int, i, n) {
        vector<Triple> g1;
        int prev = -i - 1;
        auto push = [&](Triple t) {
            if (g1.empty() || t.delta != g1.back().delta) {
                g1.push_back(t);
            } else {
                g1.back().count += t.count;
            }
        };
        for (auto t : g) {
            if (t.start > 0 && s1[t.start - 1] == s1[i]) {
                t.start--;
                if (prev != t.start - t.delta) {
                    push(Triple{t.start, t.start - prev, 1});
                    t.start += t.delta;
                    t.count--;
                }
                if (t.count > 0) {
                    push(t);
                }
                prev = t.end();
            }
        }
        if (i >= 1 && s1[i - 1] == s1[i]) {
            push(Triple{i - 1, i - 1 - prev, 1});
        }
        g = move(g1);
        for (auto& t : g) {
            mt add = d[t.end()];
            if (t.count > 1) {
                add += cache[t.start - t.delta];
            }
            if (t.start - t.delta >= 0) {
                cache[t.start - t.delta] = add;
            }
            d[i + 1] += add;
        }
    }
    out << d[n] << endl;
}


int main() {
    solve(cin, cout);
    return 0;
}

Full text and comments »

TooDumbToWin's blog

Prizes