Submission #393662

# Submission time Handle Problem Language Result Execution time Memory
393662 2021-04-24T08:09:40 Z Karliver Type Printer (IOI08_printer) C++14
100 / 100
204 ms 78928 KB

#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;




}

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();
    }
}
int main() {



    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    another();
    // 5 4 3 2 1



}

Compilation message

printer.cpp: In lambda function:
printer.cpp:259:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |         for(int i = 0;i < s.size();++i) {
      |                       ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4264 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 4 ms 4812 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 5320 KB Output is correct
2 Correct 7 ms 5704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 14 ms 8424 KB Output is correct
2 Correct 30 ms 13256 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 32 ms 15088 KB Output is correct
2 Correct 16 ms 6952 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 81 ms 31536 KB Output is correct
2 Correct 176 ms 67084 KB Output is correct
3 Correct 98 ms 37580 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 69 ms 25772 KB Output is correct
2 Correct 204 ms 78928 KB Output is correct
3 Correct 111 ms 41936 KB Output is correct
4 Correct 180 ms 74892 KB Output is correct