Submission #378914

#	Time	Username	Problem	Language	Result	Execution time	Memory
378914		balbit	Nice sequence (IZhO18_sequence)	C++14	100 / 100	970 ms	44596 KiB

sequence

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

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT


#define REP(i,n) for (int i = 0; i<n; ++i)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

int a,b,L;
const int maxn = 4e5+5;
int seen[maxn];

bool dfs(int v, int c) {
    seen[v] = c;
    if (v-a>=0) {
        if (seen[v-a]) {
            if (seen[v-a] == c) return 0;
        }else{
            if (!dfs(v-a,c)) return 0;
        }
    }
    if (v+b<=L) {
        if (seen[v+b]) {
            if (seen[v+b] == c) return 0;
        }else{
            if (!dfs(v+b,c)) return 0;
        }
    }
    return 1;
}
vector<int> po;
bool dfs2(int v, int c) {
    seen[v] = c;
//    bug("try",v);
    if (v-a>=0) {
        if (seen[v-a]) {
            if (seen[v-a] == c) return 0;
        }else{
            if (!dfs2(v-a,c)) return 0;
        }
    }
    if (v+b<=L) {
        if (seen[v+b]) {
            if (seen[v+b] == c) return 0;
        }else{
            if (!dfs2(v+b,c)) return 0;
        }
    }
//    bug("wtf",v);
    po.pb(v);
    return 1;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    bug(1,2);
    int t; cin>>t;
    while (t--) {
        cin>>a>>b;
        int l = max(a,b)-1, r = a+b+1;
        while (l!=r) {
            int mid = (l+r)/2;
            L = mid;
            memset(seen, 0, sizeof seen);
            bool ok = 1;
            REP(i,L+1) {
                if (!seen[i]) {
                    if (!dfs(i, i+1)) {
                        ok = 0;
//                        bug(i);
                        break;
                    }
                }
            }
            if (ok ) {
                l = mid+1;
            }else{
                r=mid;
            }
            bug(mid, ok);
        }
        --l;
        L = l;
        cout<<l<<endl;
        memset(seen, 0,sizeof seen);
        po.clear();
        REP(i,l+1) {
            if (!seen[i]) {
                assert(dfs2(i,i+1));
            }
        }
//        bug(SZ(po));
        vector<int> re(l+1);
        REP(i, SZ(po)) {
            re[po[i]] = i;
        }
        REP(i, SZ(po)) {
            if (i) {
                cout<<re[i-1]-re[i]<<' ';
            }
        }
        cout<<endl;
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24