Submission #393689

#	Time	Username	Problem	Language	Result	Execution time	Memory
393689		Karliver	Rice Hub (IOI11_ricehub)	C++14	100 / 100	22 ms	2892 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 1e6 + 100;
const double eps = 1e-3;

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}


ll power(ll a, ll b){
    if(!b)
        return 1;
    ll c=power(a,b/2);
    c=(1LL*c*c);
    if(b%2)
        c=(1LL*c*a);
    return c;
}


int mul(int a, int b) {
    return a * 1ll * b % mod;
}
int add(int a, int b) {
    int s = (a+b);
    if (s>=mod) s-=mod;
    return s;
}

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};
const ll MOD = 1e9 + 7;
using Mint = modint<MOD>;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

template<class T>
struct Combination{
	vector<T> fact,factinv;
	Combination(int n) : fact(n + 1),factinv(n + 1){
		fact[0] = 1;
		for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
		factinv[n] = ~fact[n];
		for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
	}
	T nCr(int n,int r){
		if(n < 0 || r < 0 || n < r) return 0;
		return fact[n]  * factinv[r] *  factinv[n - r];
	}
	T factorial(int x) {
        if(x < 0)return 0;
        return fact[x];
	}
};

void done() {




}
struct UNION_FIND {
    vector<int>parent;
    vector<int>sz;

    void init(int n) {
        parent.resize(n + 1);
        sz.resize(n + 1);

        for(int i = 1;i <= n;++i) {
            parent[i] = i;
            sz[i] = 1;

        }
    }



    int find_set(int v)  {
        if(v == parent[v]) {
            return v;
        }
        return parent[v] = find_set(parent[v]);
    }
    void unite(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if(a != b) {
            if(sz[a] < sz[b]) {
                swap(a, b);
            }
            parent[b] = a;
            sz[a] += sz[b];
        }
    }



};

void solve()
{

    int n;
    cin >> n;




}
int besthub(int R, int L, int X[], ll B) {
    int l = 0;
    int r = 0;
    vector<ll> sm;
    sm.push_back(0);
    ll cost = 0;
    forn(i, R)sm.push_back(sm.back() + X[i]);   
    auto upd = [&]() {
        int mid = (l + r) / 2;
        cost = 0;
        cost += (mid - l + 1)* 1ll * X[mid];
        cost -= sm[mid + 1] - sm[l];
        cost -= (r - mid + 1) *1ll *  X[mid];
        cost += sm[r + 1] - sm[mid];


    };
    int ans = 0;
    while(l < R) {
        while(r < R - 1 && cost <= B) {
            ++r;
            upd();
        }
        if(cost > B) {
            r--;
            upd();
        }
        ckma(ans, r - l + 1);
        ++l;
    }
    return ans;
}

void emer() {

    // start from here
    //
    //

    int n;
    cin >> n;
    int m;
    cin >> m;

    vector<vector<int>> g(n, vector<int>(m));
    forn(i, n) forn(j, m) cin >> g[i][j];
    forn(i,n)sort(g[i].begin(), g[i].end());

    for(int i = 1;i < n;++i)reverse(g[i].begin(), g[i].end());
    forn(i, n) {
        forn(j, m) {
            cout << g[i][j] << ' ';
        }
        cout << '\n';
    }


}
void another() {

    struct node {
        vector<int> to;
        int cnt;
        node() {
            to.assign(27, INF);

            cnt = 0;
        }
    };
    int n;
    cin >> n;
    vector<node> ls;
    vector<int> dep(N, 0);
    ls.push_back(node());
    auto add = [&](string s) {
        int now = 0;
        for(int i = 0;i < s.size();++i) {
            if(ls[now].to[s[i] - 'a'] == INF) {
                ls[now].to[s[i] - 'a'] = (int)ls.size();
                ls.push_back(node());
            }
            now = ls[now].to[s[i] - 'a'];
            ckma(dep[now], (int)s.size());
        }
        ls[now].cnt++;

    };


    vector<string> s(n);
    forn(i, n) {
        cin >> s[i];
        add(s[i]);
    }
    vector<char>ans;
    function<void(int)> dfs = [&](int v) {
        if(!n)return;
        if(ls[v].cnt) {
            ans.push_back('P');
            if(--n == 0)return;
        }
        vector<pairs> k;
        forn(i, 26) if(ls[v].to[i] != INF)k.push_back({dep[ls[v].to[i]], i});
        sort(k.begin(), k.end());
        for(auto c : k) {
            ans.push_back(char('a' + c.second));
            dfs(ls[v].to[c.second]);
        }
        if(n) {
            ans.push_back('-');
        }
    };
    dfs(0);
    cout << ans.size() << '\n';
    for(auto c : ans)cout << c << '\n';




}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}

Compilation message (stderr)

ricehub.cpp: In lambda function:
ricehub.cpp:291:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  291 |         for(int i = 0;i < s.size();++i) {
      |                       ~~^~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32