#850658 (C++17) No.2247 01 ZigZag

提出ソース

結果

問題	No.2247 01 ZigZag
ユーザー	erbowl
提出日時	2023-03-17 22:54:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	9 ms / 2,000 ms
コード長	16,303 bytes
コンパイル時間	2,889 ms
コンパイル使用メモリ	226,300 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-18 20:17:02
合計ジャッジ時間	4,367 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	4 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	6 ms 4,348 KB
testcase_06	AC	4 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	7 ms 4,348 KB
testcase_09	AC	5 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	4 ms 4,348 KB
testcase_12	AC	6 ms 4,348 KB
testcase_13	AC	3 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	6 ms 4,348 KB
testcase_16	AC	8 ms 4,348 KB
testcase_17	AC	6 ms 4,348 KB
testcase_18	AC	1 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	3 ms 4,348 KB
testcase_22	AC	8 ms 4,348 KB
testcase_23	AC	3 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	7 ms 4,348 KB
testcase_26	AC	6 ms 4,348 KB
testcase_27	AC	7 ms 4,348 KB
testcase_28	AC	6 ms 4,348 KB
testcase_29	AC	5 ms 4,348 KB
testcase_30	AC	8 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	6 ms 4,348 KB
testcase_33	AC	5 ms 4,348 KB
testcase_34	AC	5 ms 4,348 KB
testcase_35	AC	5 ms 4,348 KB
testcase_36	AC	5 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	3 ms 4,348 KB
testcase_40	AC	2 ms 4,348 KB
testcase_41	AC	7 ms 4,348 KB
testcase_42	AC	6 ms 4,348 KB
testcase_43	AC	2 ms 4,348 KB
testcase_44	AC	2 ms 4,348 KB
testcase_45	AC	9 ms 4,348 KB
testcase_46	AC	9 ms 4,348 KB
testcase_47	AC	2 ms 4,348 KB
testcase_48	AC	2 ms 4,348 KB
testcase_49	AC	2 ms 4,348 KB
testcase_50	AC	1 ms 4,348 KB
testcase_51	AC	2 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;
#define int long long


struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (x > y) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};



// modint (replace MODS[0] on runtime)
// vector<int> MODS = { 1000000007 };
vector<int> MODS = { 998244353 };
template<int IND = 0> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MODS[IND]) {
        if (val < 0) val += MODS[IND];
    }
    constexpr int getmod() const { return MODS[IND]; }
    constexpr Fp operator - () const noexcept {
        return val ? MODS[IND] - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MODS[IND]) val -= MODS[IND];
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MODS[IND];
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MODS[IND];
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MODS[IND], u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MODS[IND];
        if (val < 0) val += MODS[IND];
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream& is, Fp<IND>& x) noexcept {
        is >> x.val;
        x.val %= MODS[IND];
        if (x.val < 0) x.val += MODS[IND];
        return is;
    }
    friend constexpr ostream& operator << (ostream& os, const Fp<IND>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<IND> modpow(const Fp<IND>& r, long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return modpow(modinv(r), -n);
        auto t = modpow(r, n / 2);
        t = t * t;
        if (n & 1) t = t * r;
        return t;
    }
    friend constexpr Fp<IND> modinv(const Fp<IND>& r) noexcept {
        long long a = r.val, b = MODS[IND], u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<IND>(u);
    }
};


// Binomial coefficient
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};



bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}
// Segment Tree
template<class Monoid> struct SegTree {
    using Func = function<Monoid(Monoid, Monoid)>;
    int N;
    Func F;
    Monoid IDENTITY;
    int SIZE_R;
    vector<Monoid> dat;

    /* initialization */
    SegTree() {}
    SegTree(int n, const Func f, const Monoid &identity)
    : N(n), F(f), IDENTITY(identity) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, IDENTITY);
    }
    void init(int n, const Func f, const Monoid &identity) {  
        N = n;
        F = f;
        IDENTITY = identity;
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, IDENTITY);
    }
    
    /* set, a is 0-indexed */
    /* build(): O(N) */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k)
            dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* update a, a is 0-indexed, O(log N) */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = v;
        while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* get [a, b), a and b are 0-indexed, O(log N) */
    Monoid get(int a, int b) {
        Monoid vleft = IDENTITY, vright = IDENTITY;
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; 
        left >>= 1, right >>= 1) {
            if (left & 1) vleft = F(vleft, dat[left++]);
            if (right & 1) vright = F(dat[--right], vright);
        }
        return F(vleft, vright);
    }
    Monoid all_get() { return dat[1]; }
    Monoid operator [] (int a) { return dat[a + SIZE_R]; }
    
    /* get max r that f(get(l, r)) = True (0-indexed), O(log N) */
    /* f(IDENTITY) need to be True */
    int max_right(const function<bool(Monoid)> f, int l = 0) {
        if (l == N) return N;
        l += SIZE_R;
        Monoid sum = IDENTITY;
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(F(sum, dat[l]))) {
                while (l < SIZE_R) {
                    l = l * 2;
                    if (f(F(sum, dat[l]))) {
                        sum = F(sum, dat[l]);
                        ++l;
                    }
                }
                return l - SIZE_R;
            }
            sum = F(sum, dat[l]);
            ++l;
        } while ((l & -l) != l);  // stop if l = 2^e
        return N;
    }

    /* get min l that f(get(l, r)) = True (0-indexed), O(log N) */
    /* f(IDENTITY) need to be True */
    int min_left(const function<bool(Monoid)> f, int r = -1) {
        if (r == 0) return 0;
        if (r == -1) r = N;
        r += SIZE_R;
        Monoid sum = IDENTITY;
        do {
            --r;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(F(dat[r], sum))) {
                while (r < SIZE_R) {
                    r = r * 2 + 1;
                    if (f(F(dat[r], sum))) {
                        sum = F(dat[r], sum);
                        --r;
                    }
                }
                return r + 1 - SIZE_R;
            }
            sum = F(dat[r], sum);
        } while ((r & -r) != r);
        return 0;
    }
    
    /* debug */
    void print() {
        for (int i = 0; i < N; ++i) {
            cout << (*this)[i];
            if (i != N-1) cout << ",";
        }
        cout << endl;
    }
};

struct RollingHash {
    static const int base1 = 1007, base2 = 2009;
    static const int mod1 = 1000000007, mod2 = 1000000009;
    vector<long long> hash1, hash2, power1, power2;

    // construct
    RollingHash(const string &S) {
        int n = (int)S.size();
        hash1.assign(n+1, 0), hash2.assign(n+1, 0);
        power1.assign(n+1, 1), power2.assign(n+1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
    }
    
    // get hash value of S[left:right]
    inline long long get(int l, int r) const {
        long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
        if (res1 < 0) res1 += mod1;
        long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
        if (res2 < 0) res2 += mod2;
        return res1 * mod2 + res2;
    }

    // get hash value of S
    inline long long get() const {
        return hash1.back() * mod2 + hash2.back();
    }

    // get lcp of S[a:] and S[b:]
    inline int getLCP(int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }

    // get lcp of S[a:] and T[b:]
    inline int getLCP(const RollingHash &T, int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != T.get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }
};


vector<bool> isprime;
vector<int> Era(int n) {
    isprime.resize(n, true);
    vector<int> res;
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n; ++i) isprime[i] = true;
    for (int i = 2; i < n; ++i) {
        if (isprime[i]) {
            res.push_back(i);
            for (int j = i*2; j < n; j += i) isprime[j] = false;
        }
    }
    return res;
}


// 整数値 x にハッシュ値を割り当てる関数
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM =    
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
} rng;


struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> mebius;
    vector<int> min_factor;

    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      mebius(MAX+1, 1),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            mebius[i] = -1;
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if ((j / i) % i == 0) mebius[j] = 0;
                else mebius[j] = -mebius[j];
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }

    // prime factorization
    vector<pair<int,int>> prime_factors(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }

    // enumerate divisors
    vector<int> divisors(int n) {
        vector<int> res({1});
        auto pf = prime_factors(n);
        for (auto p : pf) {
            int n = (int)res.size();
            for (int i = 0; i < n; ++i) {
                int v = 1;
                for (int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        return res;
    }
};



long long GCD(long long x, long long y) {
    if (y == 0) return x;
    return GCD(y, x % y);
}



// matrix
template<int MOD> struct Matrix {
    vector<vector<long long> > val;
    Matrix(int n, int m, long long x = 0) : val(n, vector<long long>(m, x)) {}
    void init(int n, int m, long long x = 0) {val.assign(n, vector<long long>(m, x));}
    size_t size() const {return val.size();}
    inline vector<long long>& operator [] (int i) {return val[i];}
};

template<int MOD> ostream& operator << (ostream& s, Matrix<MOD> A) {
    s << endl; 
    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < A[i].size(); ++j) {
            s << A[i][j] << ", ";
        }
        s << endl;
    }
    return s;
}
ll MODD = 0;
template<int MOD> Matrix<MOD> operator * (Matrix<MOD> A, Matrix<MOD> B) {
    Matrix<MOD> R(A.size(), B[0].size());
    for (int i = 0; i < A.size(); ++i) 
        for (int j = 0; j < B[0].size(); ++j)
            for (int k = 0; k < B.size(); ++k) 
                R[i][j] = (R[i][j] + A[i][k] * B[k][j] % MODD) % MODD; 
    return R;
}

template<int MOD> Matrix<MOD> pow(Matrix<MOD> A, long long n) {
    Matrix<MOD> R(A.size(), A.size());
    for (int i = 0; i < A.size(); ++i) R[i][i] = 1;
    while (n > 0) {
        if (n & 1) R = R * A;
        A = A * A;
        n >>= 1;
    }
    return R;
}

string solve(ll N, ll M, ll K){
    string tmp = "";
    for (int i = 0; i < N; i++) {
        tmp += '0';
    }
    for (int i = 0; i < M; i++) {
        tmp += '1';
    }
    vector<string> koho;
    
    do {
        ll cnt = 0;
        for (int i = 1; i < N+M; i++) {
            if(tmp[i]!=tmp[i-1])cnt++;
        }
        if(cnt==K){
            koho.push_back(tmp);
            // std::cout << tmp << std::endl;
        }
    }while(next_permutation(tmp.begin(),tmp.end()));
    sort(koho.begin(),koho.end());
    if(koho.size()==0){
        std::cout << -1 << std::endl;
    }else{
        std::cout << koho[0] << std::endl;
    }
    return tmp;
}

signed solve2(ll n,ll m,ll k){
    ll orin = n;
    ll orim = m;
    if(k==0){
        if(n==0){
            for (int i = 0; i < m; i++) {
                std::cout << "1";
            }
                std::cout << std::endl;
            return 0;
        }else if(m==0){
            for (int i = 0; i < n; i++) {
                std::cout << 0;
            }
            std::cout  << std::endl;
            return 0;
        }else{
            std::cout << -1 << std::endl;
            return 0;
        }
    }
    if(n==0||m==0){
        std::cout << -1 << std::endl;
        return 0;
    }
    for (int i = 1; i < k; i++) {
        if(i%2==1){
            if(n>=1){
                n--;
                if(n==0){
                    if(m>1){
                        m--;
                    }else{
                        std::cout << -1 << std::endl;
                        return 0;
                    }
                }
            }else{
                std::cout << -1 << std::endl;
                return 0;
            }
        }else{
            if(m>=2){
                if(n==0){
                    std::cout << -1 << std::endl;
                    return 0;
                }else{
                    m--;
                    
                }
            }else{
                std::cout << -1 << std::endl;
                return 0;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << 0;
    }
    for (int i = 0; i < orim-m; i++) {
        std::cout << "10";
    }
    for (int i = 0; i < m; i++) {
        std::cout << 1;
    }
    for (int i = 0; i < orin-n-(orim-m); i++) {
        std::cout << 0;
    }
    std::cout << std::endl;
    return 0;
}

signed main(){
    ll n,m,k;
    std::cin >> n>>m>>k;
    // for (int i = 0; i < k; i++) {
        // solve(n,m,i);
        // solve2(n,m,i);
        // std::cout << std::endl;
        // std::cout << "---" << std::endl;
    // }
    solve2(n,m,k);
}

yukicoder

結果

テストケース

ソースコード