oj.uz

Submission #393689

# Submission time Handle Problem Language Result Execution time Memory
393689 2021-04-24T09:02:37 Z Karliver Rice Hub (IOI11_ricehub) C++14
100 / 100
 22 ms 2892 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 300 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 444 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 4 ms 952 KB Output is correct
3 Correct 17 ms 2892 KB Output is correct
4 Correct 17 ms 2892 KB Output is correct
5 Correct 8 ms 1480 KB Output is correct
6 Correct 8 ms 1432 KB Output is correct
7 Correct 22 ms 2568 KB Output is correct
8 Correct 15 ms 2532 KB Output is correct
9 Correct 8 ms 1352 KB Output is correct
10 Correct 8 ms 1352 KB Output is correct
11 Correct 17 ms 2880 KB Output is correct
12 Correct 17 ms 2836 KB Output is correct
13 Correct 9 ms 1516 KB Output is correct
14 Correct 8 ms 1480 KB Output is correct
15 Correct 13 ms 2500 KB Output is correct
16 Correct 15 ms 2448 KB Output is correct
17 Correct 15 ms 2756 KB Output is correct
18 Correct 15 ms 2756 KB Output is correct
19 Correct 16 ms 2756 KB Output is correct
20 Correct 16 ms 2756 KB Output is correct