#856587 (C++23) No.2247 01 ZigZag

• 問題: No.2247 01 ZigZag
• ユーザー: VvyLw
• 提出日時: 2023-04-05 20:49:34
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 712 ms / 2,000 ms
• コード長: 18,709 bytes
• コンパイル時間: 3,033 ms
• コンパイル使用メモリ: 256,104 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-10-02 02:42:32
• 合計ジャッジ時間: 9,982 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	221 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	7 ms; 5,248 KB
testcase_06	AC	51 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	351 ms; 5,248 KB
testcase_09	AC	175 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	108 ms; 5,248 KB
testcase_12	AC	8 ms; 5,248 KB
testcase_13	AC	24 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	6 ms; 5,248 KB
testcase_16	AC	36 ms; 5,248 KB
testcase_17	AC	429 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	2 ms; 5,248 KB
testcase_21	AC	6 ms; 5,248 KB
testcase_22	AC	303 ms; 5,248 KB
testcase_23	AC	56 ms; 5,248 KB
testcase_24	AC	2 ms; 5,248 KB
testcase_25	AC	162 ms; 5,248 KB
testcase_26	AC	66 ms; 5,248 KB
testcase_27	AC	10 ms; 5,248 KB
testcase_28	AC	538 ms; 5,248 KB
testcase_29	AC	337 ms; 6,816 KB
testcase_30	AC	499 ms; 6,816 KB
testcase_31	AC	3 ms; 6,820 KB
testcase_32	AC	506 ms; 6,820 KB
testcase_33	AC	182 ms; 6,816 KB
testcase_34	AC	136 ms; 6,816 KB
testcase_35	AC	52 ms; 6,824 KB
testcase_36	AC	205 ms; 6,816 KB
testcase_37	AC	11 ms; 6,820 KB
testcase_38	AC	11 ms; 6,816 KB
testcase_39	AC	55 ms; 6,820 KB
testcase_40	AC	1 ms; 6,816 KB
testcase_41	AC	2 ms; 6,816 KB
testcase_42	AC	2 ms; 6,816 KB
testcase_43	AC	2 ms; 6,820 KB
testcase_44	AC	2 ms; 6,816 KB
testcase_45	AC	711 ms; 6,816 KB
testcase_46	AC	712 ms; 6,816 KB
testcase_47	AC	2 ms; 6,816 KB
testcase_48	AC	2 ms; 6,820 KB
testcase_49	AC	1 ms; 6,816 KB
testcase_50	AC	2 ms; 6,816 KB
testcase_51	AC	1 ms; 6,820 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

// --------------------------------------------------------------------------------------------------------------

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

namespace VvyLw {
void wa_haya_exe() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
}
void solve();
}; // VvyLw

mt19937 Random() {
    random_device seed_gen;
    mt19937 engine {seed_gen()};
    return engine;
}

// --------------------------------------------------------------------------------------------------------------

template <class T> using V = vector<T>;
template <class T, class U> using P = pair<T,U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqr = priority_queue<T,V<T>,greater<T>>;
template <class T, class U> using pqs = priority_queue<P<T,U>>;
template <class T, class U> using pqrs = priority_queue<P<T,U>,V<P<T,U>>,greater<P<T,U>>>;
template <class T, class U> bool chmax(T& a, const U& b) { if (a<b) { a=b; return 1; } return 0; }
template <class T, class U> bool chmin(T& a, const U& b) { if (a>b) { a=b; return 1; } return 0; }
template <class T, class U> bool overflow_if_add(T a, U b) { return (numeric_limits<T>::max()-a)<b; }
template <class T, class U> bool overflow_if_mul(T a, U b) { return (numeric_limits<T>::max()/a)<b; }
using ll = long long;
using ld = long double;
using uint = unsigned;
using ul = unsigned long long;
using vi = V<ll>;
using vu = V<ul>;
using vd = V<ld>;
using vc = V<char>;
using vs = V<string>;
using vb = V<bool>;
using wi = V<vi>;
using wu = V<vu>;
using wd = V<vd>;
using wc = V<vc>;
using ws = V<vs>;
using wb = V<vb>;
using pi = P<int,int>;
using pl = P<ll,ll>;
using pd = P<ld,ld>;
using pc = P<char,char>;
using ps = P<string,string>;
const int MOD = 998244353;
const int M0D = 1000000007;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const ld DINF = numeric_limits<ld>::infinity();
const double PI = acos(-1);

#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0; i<n; ++i)
#define rep2(i,n) for(ll i=0; i<n; ++i)
#define rep3(i,a,b) for(ll i=a; i<b; ++i)
#define rep4(i,a,b,c) for(ll i=a; i<b; i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rvp1(n) for(ll i=n-1; i>=0; i--)
#define rvp2(i,n) for(ll i=n-1; i>=0; i--)
#define rvp3(i,a,b) for(ll i=b-1; i>=a; i--)
#define rvp4(i,a,b,c) for(ll i=b-1; i>=a; i-=c)
#define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__)
#define all1(v) v.begin(),v.end()
#define all2(v,a) v.begin(),v.begin()+a
#define all3(v,a,b) v.begin()+a,v.begin()+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(v) v.rbegin(),v.rend()
#define rall2(v,a) v.rbegin(),v.rbegin()+a
#define rall3(v,a,b) v.rbegin()+a,v.rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define each1(elem,v) for(auto &elem: v)
#define each2(x,y,v) for(auto &[x,y]: v)
#define each3(x,y,z,v) for(auto &[x,y,z]: v)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define sqrp1(n) for(ll i=0; i*i<n; ++i)
#define sqrp2(i,n) for(ll i=0; i*i<n; ++i)
#define sqrp3(i,a,b) for(ll i=a; i*i<b; ++i)
#define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__)
#define irp(it,v) for(auto it=v.begin(); it!=v.end(); ++it)
#define ir(it,v) for(auto it=v.begin(); it!=v.end();)
#define FE(v,f) for_each(all(v),f)

namespace IO {
template <class T> void scan(T& a) { cin >> a; }
template <class T, class U> void scan(P<T,U>& p) { scan(p.first); scan(p.second); }
template <class T> void scan(V<T>& a) { for(auto &i: a) scan(i); }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail) { scan(head); in(tail...); }
template <class T> void print(const T& a) { cout << a; }
template <class T, class U> void print(const P<T,U>& p) { print(p.first); cout<<" "; print(p.second); }
template <class T> void print(const V<T>& a) { if(!a.empty()){ print(a[0]); for(auto i=a.begin(); ++i!=a.end();){ cout<<" "; print(*i); } } }
void out(){ cout<<"\n"; }
template <class T> void out(const T& t){ print(t); cout<<"\n"; }
template <class Head, class... Tail> void out(const Head& head, const Tail&... tail) { print(head); cout<<" "; out(tail...); }
template <class T> void vout(V<T>& v) { FE(v,[](T x){out(x);}); }
}; // IO
using namespace IO;
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size); in(name)
#define WEC(type,name,h,w) V<V<type>> name(h,V<type>(w)); in(name)
#define Fix(x) cout<<fixed<<setprecision(x);
#define fin(...) { out(__VA_ARGS__); return; }

namespace yesno_sys {
inline void YES(bool ok=1) { out(ok?"YES":"NO"); }
inline void NO(bool ok=1) { YES(!ok); }
inline void Yes(bool ok=1) { out(ok?"Yes":"No"); }
inline void No(bool ok=1) { Yes(!ok); }
inline void yes(bool ok=1) { print(ok?"yes":"no"); }
inline void no(bool ok=1) { yes(!ok); }
inline void yn(bool ok, string yes, string no){ out(ok?yes:no); }
inline void ny(bool ok, string yes, string no){ yn(!ok,yes,no); }
}; // yesno_sys
using namespace yesno_sys;

//#define smp(v,w,size,eng) sample(all(v),back_inserter(w),size,eng)
/*#define vsum1(v) accumulate(all(v),0LL)
#define vsum2(v,a) accumulate(all(v,a),0LL)
#define vsum3(v,a,b) accumulate(all(v,a,b),0LL)
#define vsum(...) overload3(__VA_ARGS__,vsum3,vsum2,vsum1)(__VA_ARGS__)
#define vdsum1(v) accumulate(all(v),0.0L)
#define vdsum2(v,a) accumulate(all(v,a),0.0LL)
#define vdsum3(v,a,b) accumulate(all(v,a,b),0.0L)
#define vdsum(...) overload3(__VA_ARGS__,vdsum3,vdsum2,vdsum1)(__VA_ARGS__)
#define vmul1(v) accumulate(all(v),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul2(v,a) accumulate(all(v,a),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul3(v,a,b) accumulate(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul(...) overload3(__VA_ARGS__,vmul3,vmul2,vmul1)(__VA_ARGS__)//*/
#define vsum1(v) reduce(all(v),0LL)
#define vsum2(v,a) reduce(all(v,a),0LL)
#define vsum3(v,a,b) reduce(all(v,a,b),0LL)
#define vsum(...) overload3(__VA_ARGS__,vsum3,vsum2,vsum1)(__VA_ARGS__)
#define vdsum1(v) reduce(all(v),0.0L)
#define vdsum2(v,a) reduce(all(v,a),0.0LL)
#define vdsum3(v,a,b) reduce(all(v,a,b),0.0L)
#define vdsum(...) overload3(__VA_ARGS__,vdsum3,vdsum2,vdsum1)(__VA_ARGS__)
#define vmul1(v) reduce(all(v),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul2(v,a) reduce(all(v,a),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul3(v,a,b) reduce(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul(...) overload3(__VA_ARGS__,vmul3,vmul2,vmul1)(__VA_ARGS__)//*/
#define chrpb(s,c) s.push_back((char)(c))
namespace zia_qu {
template <class T> void rev(T& v){ reverse(all(v)); }
template <class T> void Sort(T& v){ sort(all(v)); }
template <class T> void Sortt(T& v){ sort(rall(v)); }
template <class T> T Min(const T& v){ return *min_element(all(v)); }
template <class T> T Max(const T& v){ return *max_element(all(v)); }
template <class T, class I> inline ll dst(T& v, I itr){ return distance(v.begin(),itr); }
template <class T, class U> T LB(const V<T>& v, U x){ return dst(v,lower_bound(all(v),x)); }
template <class T, class U> T UB(const V<T>& v, U x){ return dst(v,upper_bound(all(v),x)); }
template <class T, class U> bool BS(const V<T>& v, U x){ return binary_search(all(v),x); }
template <class T> bool All(T& v, bool fn){ return all_of(all(v),fn); }
template <class T> bool Exist(T& v, bool fn){ return any_of(all(v),fn); }
template <class T, class U> ll Find(T& v, const U x){ return dst(v.begin(),find(all(v),x)); }
template <class T> T Count(V<T>& v, ll x) { Sort(v); return UB(v,x)-LB(v,x); }
template <class T> ul cntif(T& v, bool fn){ return count_if(all(v),fn); }
template <class T, class U> void rpl(T& v, bool fn, U r){ replace_if(all(v),fn,r); }
template <class T> V<T> iot(T n, T init){ V<T> a(n); iota(all(a),init); return a;}
template <class T, class U> void ers(T& v, U x){ v.erase(remove(all(v),x),v.end()); }
template <class T> ul unq(T& v){ Sort(v); v.erase(unique(all(v)),v.end()); return v.size(); }
template <class T, class U> void cp(const V<T>& v, V<T> u){ copy(all(v),back_inserter(u)); }
template <class T> void rtt(T& v, ul idx){ rotate(all(v,idx),v.end()); }
template <class T> V<T> psum(V<T>& v) {
    V<T> s(v.size());
    partial_sum(all(v),s.begin());
    rtt(s,v.size());
    return s;
}
template <class T> V<T> adf(V<T>& v){ V<T> res(v.size()-1); adjacent_difference(all(v),res.begin()); return res; }
}; // zia qu

namespace Lady_sANDy {
ll Mod(ll x, ll m){ return (x+m)%m; }
ul Pow(ul a, uint b) { 
    ul res=1;
    while(b>0) {
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
ll Ceil(ld x, ll m){ return ceil(x/m); }
ld Round(ld x, ll m, uint fx){ if(fx==0) return (ll)round(x/m); else { ul y=Pow(10,fx+1); return round((x*y)/m/y); } }
template <class T> inline T IP(const V<T>& v, const V<T>& u, T init){ return inner_product(all(v),u.begin(),init); }
ll popcnt(ll x){ return __builtin_popcountll(x); }
template<class... T> constexpr auto symin(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); }
template<class... T> constexpr auto symax(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); }
template <class T, class U> T kymin(map<T,U> m){ return m.begin()->first; }
template <class T, class U> T kymax(map<T,U> m){ return m.rbegin()->first; }
template <class T> T stmin(set<T> s){ return *s.begin(); }
template <class T> T stmax(set<T> s){ return *s.rbegin(); }
}; // Lady s&y
#define debug(...) { print(#__VA_ARGS__); print(": "); out(__VA_ARGS__); }
#define elif else if
#define scp(a,x,b) a<=x&&x<=b
#define each_idx(el,v) &el-&v[0]
//#define Mid(a,b) midpoint(a,b)
#define mp make_pair
#define mt make_tuple
#define bit_check(bit,tar) (tar>>bit)&1
#define nxp(x) next_permutation(all(x))
#define prp(x) prev_permutation(all(x))
#define str_rpl(s,a,b) regex_replace(s,regex(a),b)
#define ast(bool) assert(bool)

namespace Heileden {
/* Permutation Sample
template <class T> inline void nPr(V<T>& v) {
    Sort(v);
    do {out(v);} while(nxp(v));
}//*/

// divisor
template <class T> inline V<T> divisor(T n) {
    V<T> div;
    sqrp(i,1,n+1) {
        if(n%i==0) {
            div.emplace_back(i);
            if(i*i!=n) div.emplace_back(n/i);
        }
    }
    Sort(div);
    return div;
}

// prime judge
inline bool is_prime(ul n) {
    sqrp(i,2,n+1) if(n%i==0) return 0;
    return 1;
}

// Siege of Eratosthenes
inline vb SoE(ll n) {
    vb prime(n+1,1);
    if(n>=0) prime[0]=0;
    if(n>=1) prime[1]=0;
    sqrp(i,2,n+1) {
        if(!prime[i]) continue;
        rep(j,i*i,n+1,i) prime[j]=0;
    }
    return prime;
}

// prime factor
template <class T> inline V<P<T,T>> prmfct(T n) {
    V<P<T,T>> res;
    rep(i,2,n+1) {
        if(n%i!=0) continue;
        T tmp=0;
        while(n%i==0) {
            tmp++;
            n/=i;
        }
        res.emplace_back(i,tmp);
    }
    if(n!=1) res.emplace_back(n,1);
    return res;
}

// square judge
inline bool is_squere(ll n) {
    ll r=(ll)floor(sqrt((ld)n));
    return r*r==n;
}

/* BFS Sample
template <class T> inline void bfs(V<V<T>>& g, T start, vb& visited) {
    queue<T> que;
    que.emplace(start);
    visited[start]=1;
    while(!que.empty()) {
        T v=que.front();
        que.pop();
        each(nv,g[v]) {
            if(!visited[nv]) {
                visited[nv]=1;
                que.emplace(nv);
            }
        }
    }
}//*/

/* DFS Sample
template <class T> inline void dfs(V<V<T>>& g, T v, vb& visited) {
    visited[v]=1;
    each(nv,g[v]) if(!visited[nv]) dfs(g,nv,visited);
}//*/
}; // Heileden

// UnionFind-Tree
struct UnionFind {
    vi par,sz;
    UnionFind(ll n) {
        par.resize(n,0);
        sz.resize(n,0);
        rep(n) makeTree(i);
    }
    void makeTree(ll x) {
        par[x]=x;
        sz[x]=1;
    }
    bool same(ll x, ll y) { return root(x)==root(y); }
    bool unite(ll x, ll y) {
        x=root(x); y=root(y);
        if(x==y) return 0;
        if(sz[x]>sz[y]) {
            par[y]=x;
            sz[x]+=sz[y];
        }
        else {
            par[x]=y;
            sz[y]+=sz[x];
        }
        return 1;
    }
    ll root(ll x) {
        if(x!=par[x]) par[x]=root(par[x]);
        return par[x];
    }
    ll size(ll x) { return sz[root(x)]; }
};

// Segment-Tree
template <class T> struct SegTree {
    const T e = numeric_limits<T>::max();
    function<T(T, T)> fx = [](T x1, T x2){ return min(x1, x2); };
    ll n;
    V<T> dat;
    SegTree(ll n_) : n(), dat(n_ * 4, e) {
        ll x = 1;
        while (n_ > x) x *= 2;
        n = x;
    }
    void set(ll i, T x){ dat[i + n - 1] = x; }
    void build(){ rvp(k,n-1) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]); }
    void update(ll i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    T query(ll a, ll b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a || b <= l) return e;
        elif (a <= l && r <= b) return dat[k];
        else {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
    ll find_rightest(ll a, ll b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
    ll find_leftest(ll a, ll b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
    ll find_rightest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) return a - 1;
        elif (k >= n - 1) return (k - (n - 1));
        else {
            ll vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (vr != a - 1) return vr;
            else return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
        }
    }
    ll find_leftest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) return b;
        elif (k >= n - 1) return (k - (n - 1));
        else {
            ll vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            if (vl != b) return vl;
            else return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
        }
    }
};

// Modint
template <int mod> struct Modint {
    int val;
    constexpr Modint() : val(0){}
    constexpr Modint(ll x) : val(x >= 0 ? x % mod : (mod - (-x) % mod) % mod){}
    int getmod(){ return mod; }
    constexpr Modint &operator+=(const Modint &p) {
        if ((val += p.val) >= mod) val -= mod;
        return *this;
    }
    constexpr Modint &operator-=(const Modint &p) {
        if((val += mod - p.val) >= mod) val -= mod;
        return *this;
    }
    constexpr Modint &operator*=(const Modint &p) {
        val = (int)(1LL * val * p.val % mod);
        return *this;
    }
    constexpr Modint &operator/=(const Modint &p) {
        *this *= p.inverse();
        return *this;
    }
    constexpr Modint operator-() const { return Modint(-val); }
    constexpr Modint operator+(const Modint &p) const { return Modint(*this) += p; }
    constexpr Modint operator-(const Modint &p) const { return Modint(*this) -= p; }
    constexpr Modint operator*(const Modint &p) const { return Modint(*this) *= p; }
    constexpr Modint operator/(const Modint &p) const { return Modint(*this) /= p; }
    constexpr bool operator==(const Modint &p) const { return val == p.val; }
    constexpr bool operator!=(const Modint &p) const { return val != p.val; }
    constexpr Modint inv() const {
        int a=val, b=mod, u=1, v=0, t;
        while(b>0) {
            t=a/b;
            swap(a -= t*b,b);
            swap(u -= t*v,v);
        }
        return Modint(u);
    }
    constexpr Modint pow(ll n) const {
        Modint res(1), mul(val);
        while(n>0) {
            if(n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    friend ostream &operator<<(ostream &os, const Modint &p) { return os << p.val; }
    friend istream &operator>>(istream &is, Modint &a) {
        ll t;
        is >> t;
        a=Modint<mod>(t);
        return (is);
    }
    static int get_mod() { return mod; }
};
template <class T> struct Comb {
    V<T> fact_, fact_inv_, inv_;
    Comb(){}
    Comb(int SIZE) : fact_(SIZE, 1), fact_inv_(SIZE, 1), inv_(SIZE, 1){ init(SIZE); }
    void init(int SIZE) {
        fact_.assign(SIZE, 1), fact_inv_.assign(SIZE, 1), inv_.assign(SIZE, 1);
        int mod = fact_[0].getmod();
        rep(i,2,SIZE) {
            fact_[i] = fact_[i - 1] * i;
            inv_[i] = -inv_[mod % i] * (mod / i);
            fact_inv_[i] = fact_inv_[i - 1] * inv_[i];
        }
    }
    T nCr(int n, int r) {
        ast(!(n < r));
        ast(!(n < 0 || r < 0));
        return fact_[n] * fact_inv_[r] * fact_inv_[n - r];
    }
    T nHr(int n, int r) {
        ast(!(n < 0 || r < 0));
        return nCr(n + r - 1, r);
    }
    T fact(int n) {
        ast(!(n < 0));
        return fact_[n];
    }
    T fact_inv(int n) {
        ast(!(n < 0));
        return fact_inv_[n];
    }
    T inv(int n) {
        ast(!(n < 0));
        return inv_[n];
    }
};

//using mint = Modint<MOD>;
//using mint = Modint<M0D>;
//Comb<mint> comb(10000000);

// --------------------------------------------------------------------------------------------------------------

using namespace zia_qu;
using namespace Lady_sANDy;
using namespace Heileden;

int main() {
    VvyLw::wa_haya_exe();
    /*INT(t); while(t--)//*/
    VvyLw::solve();
}

// --------------------------------------------------------------------------------------------------------------


void VvyLw::solve() {
    INT(n,m,k);
    string s;
    rep(n) s.push_back('0');
    rep(m) s.push_back('1');
    int x=abs(n-m);
    if(x>0) x--;
    if(k>=(n+m)-x) fin(-1)
    if(k==0) if(n*m!=0) fin(-1)
    if(!(n<m && k==n+m-x-1)) k--;
    int a=1,b=0;
    rep(k) {
        if(i%2) {
            string t=s.substr(a+n-1);
            rtt(t,t.size()-1);
            s.replace(s.begin()+a+n-1,s.end(),t);
            a++;
        } else {
            string t=s.substr(b+n-1);
            rtt(t,1);
            s.replace(s.begin()+b+n-1,s.end(),t);
            b--;
        }
    }
    out(s);
}