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

• 問題: No.2247 01 ZigZag
• ユーザー: omgflaka
• 提出日時: 2023-03-24 22:28:29
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,629 ms / 2,000 ms
• コード長: 4,724 bytes
• コンパイル時間: 2,402 ms
• コンパイル使用メモリ: 207,244 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-18 17:18:46
• 合計ジャッジ時間: 12,947 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	348 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	11 ms; 5,376 KB
testcase_06	AC	74 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	199 ms; 5,376 KB
testcase_09	AC	559 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	70 ms; 5,376 KB
testcase_12	AC	139 ms; 5,376 KB
testcase_13	AC	48 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	71 ms; 5,376 KB
testcase_16	AC	312 ms; 5,376 KB
testcase_17	AC	1,113 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	20 ms; 5,376 KB
testcase_22	AC	380 ms; 5,376 KB
testcase_23	AC	48 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	762 ms; 5,376 KB
testcase_26	AC	383 ms; 5,376 KB
testcase_27	AC	3 ms; 5,376 KB
testcase_28	AC	380 ms; 5,376 KB
testcase_29	AC	597 ms; 5,376 KB
testcase_30	AC	608 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	3 ms; 5,376 KB
testcase_33	AC	3 ms; 5,376 KB
testcase_34	AC	3 ms; 5,376 KB
testcase_35	AC	2 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	2 ms; 5,376 KB
testcase_38	AC	2 ms; 5,376 KB
testcase_39	AC	2 ms; 5,376 KB
testcase_40	AC	2 ms; 5,376 KB
testcase_41	AC	2 ms; 5,376 KB
testcase_42	AC	2 ms; 5,376 KB
testcase_43	AC	2 ms; 5,376 KB
testcase_44	AC	2 ms; 5,376 KB
testcase_45	AC	1,629 ms; 5,376 KB
testcase_46	AC	1,610 ms; 5,376 KB
testcase_47	AC	2 ms; 5,376 KB
testcase_48	AC	2 ms; 5,376 KB
testcase_49	AC	2 ms; 5,376 KB
testcase_50	AC	2 ms; 5,376 KB
testcase_51	AC	2 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int> 
#define vb vector<bool> 
#define pub push_back
#define emb emplace_back
#define rep(i,a,b) for(long long i = a; i < b; i++)
#define rrep(i,a,b) for(long long i = a; i >= b; i--)
#define iterm(key,val,ok) for(auto const& [key, val]:ok)
#define all(x) x.begin(),x.end()
#define py cout<<"YES"<<endl
#define pn cout<<"NO"<<endl
#define pa cout<<ans<<endl
#define pe cout<<endl
#define mp make_pair
#define f first 
#define se second 
using pii=pair<ll,ll>;
template<typename T>             istream& operator>>(istream& is, vector<T>& v) { for (auto& i : v) is >> i;        return is; }
template<typename T>             ostream& operator<<(ostream& os, const vector<T>& v) { for (auto& i : v) os << i << " "; return os; }
template<typename T>             istream& operator>>(istream& is, pair<T, T>& v) { is >> v.first >> v.second;        return is; }
template<typename T>             ostream& operator<<(ostream& os, const pair<T, T>& v) { os << v.first << " " << v.second; return os; }
 
 
 
/*
problems with mod or small constraints are DP (2d,3d) or combo
ascii: 1=49 a=97 A=65
check edge cases and constraints CHECK FOR JUST ONE ELEMENT OR SAME NUMBERS ETC
always think about reversing a process
see if theres any dumb tricks if youre not getting it: like only having to check small values or sth
(a-b)modm = (a%m+(m-b%m))%m
mark visited after adding to queue
think about transforming representations of graphs, if some graph is too big to be represented, think about bipartite
representation, if its too small maybe you can expand according to problem to make it easier
you can also bfs on pairs of nodes, different representations of nodes etc etc
lower bound can give beyond end also (check segfaults etc if using)
many smol vectors are slowwww, use std:array instead
to search for and remove particular things fastly just use multiset, like u can use prefix multiset and find closest
value of something also like so many applications in just logn time
*/

void solve(){
    ll n,m,k;cin>>n>>m>>k;
    if((m!=n && k>2*min(n,m)) || (m==n && k>(2*m-1))){
        cout<<-1<<endl;return;
    }
    ll ini=k;
    string s="";
    if(m!=n){
        if(k==2*min(n,m)){
            if(n>m){
                while(n-((k/2)+1)){
                    s+='0';
                    n--;
                }
                while(k>1){
                    s+='0';
                    s+='1';
                    n--;
                    m--;
                    if(s.size()==2){
                        k--;
                    }
                    else{
                        k-=2;
                    }
                }
                s+='0';
                n--;
            }
            else{
                while(k>1){
                    s+='1';
                    s+='0';
                    n--;
                    m--;
                    if(s.size()==2){
                        k--;
                    }
                    else{
                        k-=2;
                    }
                }
                s+='1';
                m--;
                while(m){
                    s+='1';
                    m--;
                }
            }
        }
        else{
            //cout<<(n-(k+1)/2)<<endl;
            rep(i,0,(n-(k+2)/2)){
                s+='0';
            }
            rep(i,0,k+1){
                if(i%2==0){
                    s=s+'0';
                }
                else{
                    s=s+'1';
                    m--;
                }
            }
            while(m){
                s+='1';
                m--;
            }
        }
    }
    else{
        if(true){
            rep(i,0,(n-(k+2)/2)){
                s+='0';
            }
            rep(i,0,k+1){
                if(i%2==0){
                    s=s+'0';
                }
                else{
                    s=s+'1';
                    m--;
                }
            }
            while(m){
                s+='1';
                m--;
            }
        }
    }
    ll ans=0;
    rep(i,1,s.size()){
        if(s[i]!=s[i-1]){
            ans++;
        }
    }
    if(ans!=ini){
        rrep(i,s.size()-1,1){
            if(s[i]!=s[i-1]){
                //cout<<i-1<<endl;
                swap(s[s.size()-1],s[i-1]);break;
            }
        }
    }
    ans=0;
    rep(i,1,s.size()){
        if(s[i]!=s[i-1]){
            ans++;
        }
    }
    if(ans!=ini){
        cout<<-1<<endl;return;
    }
    cout<<s<<endl;
}
 
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}