Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Good Bye 2018 — Editorial
Difference between en1 and en2, changed 11,016 character(s)
[tutorial:1091A]↵
[tutorial:1091B]↵
[tutorial:1091C]↵
[tutorial:1091D]↵
[tutorial:1091E]↵
[tutorial:1091F]↵
[tutorial:1091G]↵
[tutorial:1091H]

<spoiler summary="Code (by arsijo)">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵

int main(){↵
    int a, b, c;↵
    cin >> a >> b >> c;↵
    cout << min(a + 2, min(b + 1, c)) * 3 - 3;↵
}↵
```↵
</spoiler>↵

[tutorial:1091B]↵

<spoiler summary="Code">↵
```↵
#include <vector>↵
#include <algorithm>↵
#include <iostream>↵

using namespace std;↵

typedef pair<int,int> pii;↵

#define x first↵
#define y second↵

int main() {↵
    int N; cin >> N;↵
    vector<pii> O(N), T(N);↵
    for (int i = 0; i < N; i++) cin >> O[i].x >> O[i].y;↵
    for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y;↵
    sort(O.begin(),O.end());↵
    sort(T.begin(),T.end());↵
    reverse(T.begin(),T.end());↵

    vector<pii> Ans(N);↵
    for (int i = 0; i < N; i++) Ans[i] = {O[i].x+T[i].x, O[i].y+T[i].y};↵
    sort(Ans.begin(),Ans.end());↵
    cout << Ans[0].x << ' ' << Ans[0].y << endl;↵
}↵
```↵
</spoiler>↵

[tutorial:1091C]↵

<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵

using namespace std;↵

typedef long long ll;↵

int main() {↵
ll N; cin >> N;↵
vector<ll> ans;↵

for (ll i = 1; i*i <= N; ++i) {↵
if (N%i==0) {↵
ans.push_back(N*(i-1)/2 + i);↵
if (i*i!=N) {↵
ans.push_back(N*(N/i-1)/2 + N/i);↵
}↵
}↵
}↵
sort(ans.begin(),ans.end());↵

for (int i = 0; i < ans.size(); ++i) {↵
cout << ans[i] << " \n"[i==ans.size()-1];↵
}↵

}↵
```↵
</spoiler>↵

[tutorial:1091D]↵

<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵

using namespace std;↵

template <unsigned int N> class Field {↵
    typedef unsigned int ui;↵
    typedef unsigned long long ull;↵
inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}↵
inline ui inv(ui a){return pow(a,N-2);}↵
public:↵
    inline Field(int x = 0) : v(x) {}↵
inline Field<N> pow(int p){return (*this)^p; }↵
inline Field<N> operator^(int p){return {(int)pow(v,(ui)p)};}↵
    inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }↵
    inline Field<N>&operator-=(const Field<N>&o) {if (v<o.v) v -= o.v-N; else v-=o.v; return *this; }↵
    inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }↵
    inline Field<N>&operator/=(const Field<N>&o) { return *this*=inv(o.v); }↵
    inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}↵
    inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}↵
    inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}↵
    inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}↵
    inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};↵
    inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }↵
    inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }↵
    inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }↵
    inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }↵
    inline bool operator==(const Field<N>&o) const { return o.v==v; }↵
inline bool operator!=(const Field<N>&o) const { return o.v!=v; }↵
inline explicit operator ui() const { return v; }↵
inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}↵
inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}↵
private: ui v;↵
};↵
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}↵
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}↵
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}↵
template<unsigned int N>Field<N> operator-(int i,const Field<N>&f){return Field<N>(i)-f;}↵
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}↵
template<unsigned int N>Field<N> operator/(int i,const Field<N>&f){return Field<N>(i)/f;}↵

typedef Field<998244353> FF;↵

int main(int argc, char* argv[]) {↵
    int n; cin >> n;↵
    auto F = FF::fact(n);↵
    auto I = FF::invfact(n);↵
    FF ans = n * F[n];↵
    for (int i = 1; i < n; ++i) ans -= F[n]*I[i];↵
    cout << ans << endl;↵
}↵
```↵
</spoiler>↵

[tutorial:1091E]↵

<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <algorithm>↵
#include <vector>↵
using namespace std;↵

#define MAXN 500000↵

int N;↵
int A[MAXN];↵
long long sum;↵

#define TOO_SMALL -1↵
#define OK 0↵
#define TOO_BIG 1↵

int is_score(int value) {↵
    vector<int> C(N+1,0);↵
    for (int i = 0; i < N; ++i) ++C[A[i]];↵
    ++C[value];↵

    int less = 0;↵
    long long left = 0, right = 0;↵
    for (int k = 0, i = 0; k <= N; k++) {↵
        int val = (i == k && (i == N || A[i] < value)) ? value : A[i++];↵
        left += val;↵
        --C[val];↵
        right -= min(val, k);↵
        less += C[k];↵
        right += N-k-less;↵
        if (left > right + (long long)(k+1)*k) {↵
            return (i == k) ? TOO_BIG : TOO_SMALL;↵
        }↵
    }↵
    return OK;↵
}↵

int main(int,char**) {↵
    ios_base::sync_with_stdio(false);↵
    ↵
    scanf("%d", &N);↵
    sum = 0;↵
    for (int i = 0; i < N; i++) {↵
        scanf("%d", A + i);↵
        sum += A[i];↵
    }↵

    sort(A,A+N,greater<int>());↵
    int parity = sum & 1;↵
    int lo = 0, hi = (N - parity) / 2, lores = -1;↵
    while (lo <= hi) {↵
        int mid = (lo + hi) / 2;↵
        if (is_score(2*mid + parity) == TOO_SMALL) {↵
            lo = mid + 1;↵
        } else {↵
            lores = mid;↵
            hi = mid - 1;↵
        }↵
    }↵
    ↵
    lo = lores; ↵
    hi = (N - parity) / 2; ↵
    int hires = -1;↵
    while (lo <= hi) {↵
        int mid = (lo + hi) / 2;↵
        if (is_score(2*mid + parity) == TOO_BIG) {↵
            hi = mid - 1;↵
        } else {↵
            hires = mid;↵
            lo = mid + 1;↵
        }↵
    }↵
    ↵
    if (lores == -1 || hires == -1) printf("-1\n"); ↵
    else {↵
        for (int i = lores; i <= hires; ++i) printf("%d ", 2*i+parity);↵
        printf("\n");↵
    }↵
}↵
```↵
</spoiler>↵

[tutorial:1091F]↵

<spoiler summary="Code">↵
```↵
#include <iostream>↵
#include <vector>↵
#include <string>↵

typedef long long ll;↵
using namespace std;↵

int main() {↵
    int N; cin >> N;↵
    vector<ll> L(N); ↵
    for (ll &l: L) cin >> l;↵
    string T; cin >> T;↵
    bool hadWater = false;↵
    ll time = 0, stamina = 0, twiceGrass = 0;↵
    for (int i = 0; i < N; ++i) {↵
        if (T[i] == 'L') {↵
            time += L[i];↵
            stamina -= L[i];↵
            if (stamina < 0) {↵
                /* not enough stamina, walk or swim "in place" to gain it */↵
                time -= stamina * (hadWater ? 3 : 5);↵
                stamina = 0;↵
            }↵
        } else if (T[i] == 'W') {↵
            hadWater = true;↵
            stamina += L[i];↵
            time += 3 * L[i];↵
        } else {↵
            stamina += L[i];↵
            time += 5 * L[i];↵
            twiceGrass += 2*L[i];   ↵
        }↵
        /* no more than stamina/2 of walking can be converted to flying to save time,↵
         * otherwise there would not be enough stamina at this point */↵
        twiceGrass = min(twiceGrass, stamina);↵
    }↵

    if (stamina > 0) {↵
        // convert walking to flying↵
        time -= (5-1) * twiceGrass/2;↵

        // convert swimming to flying↵
        time -= (3-1) * (stamina - twiceGrass)/2;↵
    }↵

    cout << time << endl;↵
}↵
```↵
</spoiler>↵

[tutorial:1091G]↵

<spoiler summary="Code (by winger)">↵
```↵
import random↵

def isPrime(n):↵
    """↵
    Miller-Rabin primality test.↵

    A return value of False means n is certainly not prime. A return value of↵
    True means n is very likely a prime.↵
    """↵
    if n!=int(n):↵
        return False↵
    n=int(n)↵
    #Miller-Rabin test for prime↵
    if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:↵
        return False↵

    if n==2 or n==3 or n==5 or n==7:↵
        return True↵
    s = 0↵
    d = n-1↵
    while d%2==0:↵
        d>>=1↵
        s+=1↵
    assert(2**s * d == n-1)↵

    def trial_composite(a):↵
        if pow(a, d, n) == 1:↵
            return False↵
        for i in range(s):↵
            if pow(a, 2**i * d, n) == n-1:↵
                return False↵
        return True↵

    for i in range(20):#number of trials↵
        a = random.randrange(2, n)↵
        if trial_composite(a):↵
            return False↵

    return True↵

def gcd(x, y):↵
    return x if y == 0 else gcd(y, x % y)↵

n = int(input())↵

divs = [n]↵

def split(parts):↵
    global divs↵
    divs = [gcd(d, p) for d in divs for p in parts if gcd(d, p) != 1]↵

while not all([isPrime(x) for x in divs]):↵
    x = random.randint(0, n - 1)↵
    g = gcd(n, x)↵
    if gcd(n, x) != 1:↵
        split([g, n // g])↵
        continue↵
    y = int(input('sqrt {}\n'.format(x * x % n)))↵
    if x == y:↵
        continue↵
    a, b = abs(x - y), x + y↵
    g = gcd(x, y)↵
    split([a // g, b // g, g])↵

print('!', len(divs), ' '.join(str(d) for d in sorted(divs)))↵
```↵
</spoiler>↵

[tutorial:1091H]↵

<spoiler summary="Code">↵
```↵
#include <vector>↵
#include <stack>↵
#include <iostream>↵
#include <algorithm>↵
#include <bitset>↵
using namespace std;↵

typedef unsigned int ui;↵
typedef long long ll;↵

struct Sieve : public std::vector<bool> {↵
    // ~10ns * n↵
explicit Sieve(ui n) : vector<bool>(n+1, true), n(n) {↵
at(0) = false;↵
if (n!=0) at(1) = false;↵
for (ui i = 2; i*i <= n; ++i) {↵
if (at(i)) for (int j = i*i; j <= n; j+=i) (*this)[j] = false;↵
}↵
}↵

vector<int> primes() const {↵
vector<int> ans;↵
for (int i=2; i<=n; ++i) if (at(i)) ans.push_back(i);↵
return ans;↵
}↵

private:↵
int n;↵
};↵

constexpr int M = 2e5;↵
auto P = Sieve{M}.primes();↵

int main() {↵
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);↵

    vector<int> G(M, 0);↵
    int Q = P.size();↵
    for (int i = 0; i < Q; ++i) {↵
        for (int j = i; j < Q; ++j) {↵
            if (ll(P[i])*P[j] >= M) break;↵
            P.push_back(P[i]*P[j]);↵
        }↵
    }↵
    ↵
    bitset<M> PB;↵
    for (int p : P) PB[p] = true;↵
    ↵
    int N, F; cin >> N >> F;↵
    PB[F] = false;↵
    ↵
    vector<bitset<M>> W(100);↵
    W[0] = PB;↵
    for (int i = 1; i < M; ++i) {↵
        while (W[G[i]][i]) G[i]++;↵
        W[G[i]] |= PB << i;↵
    }↵
    cerr << *max_element(G.begin(),G.end()) << endl;↵

    int g = 0;↵
    for (int i = 0; i < N; i++) {↵
        int r,w,b;↵
        cin >> r >> w >> b;↵
        g ^= G[w-r-1];↵
        g ^= G[b-w-1];↵
    }↵
    if (g == 0) {↵
        cout << "Bob\nAlice\n";↵
    } else {↵
        cout << "Alice\nBob\n";↵
    }↵
}↵
```↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English majk 2018-12-31 11:08:32 11016
en1 English majk 2018-12-30 20:21:54 169 Initial revision (published)