Submission #1174900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174900		hengliao	Hidden Sequence (info1cup18_hidden)	C++20	100 / 100	47 ms	416 KiB

hidden

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef int ll;

vector < int > findSequence (int n)
{
    ll cnt[2]={0, 0};
    ll mx=n/2+1;
    bool done=0;
    vll re;
    while(true){
        if(cnt[0]>=mx){
            break;
        }
        re.pb(0);
        if(!isSubsequence(re)){
            done=1;
            break;
        }
        cnt[0]++;
    }
    if(!done){
        re.clear();
        done=0;
        while(true){
            if(cnt[1]>=mx){
                break;
            }
            re.pb(1);
            if(!isSubsequence(re)){
                done=1;
                break;
            }
            cnt[1]++;
        }
        assert(done);
        cnt[0]=n-cnt[1];
    }
    else{
        cnt[1]=n-cnt[0];
    }
    vll ans(n);
    vll behind(cnt[1]+1);
    for(ll i=1;i<=cnt[1];i++){
        done=0;
        re.clear();
        ll sum=1;
        behind[i]=0;
        re.pb(1);
        for(ll rep=0;rep<i-1;rep++){
            if(sum>=mx){
                break;
            }
            re.pb(1);
            sum++;
        }
        while(true){
            if(sum>=mx){
                break;
            }
            re.pb(0);
            if(!isSubsequence(re)){
                done=1;
                break;
            }
            sum++;
            behind[i]++;
        }
        if(!done){
            done=0;
            re.clear();
            sum=1;
            behind[i]=cnt[0];
            re.pb(1);
            for(ll rep=0;rep<cnt[1]-i;rep++){
                if(sum>=mx){
                    break;
                }
                re.pb(1);
                sum++;
            }
            while(true){
                if(sum>=mx){
                    break;
                }
                vll tep;
                tep.pb(0);
                for(auto &it:re){
                    tep.pb(it);
                }
                re=tep;
                if(!isSubsequence(re)){
                    done=1;
                    break;
                }
                sum++;
                behind[i]--;
            }
        }
    }
    ll pt=n-1;
    ll pre=0;
    for(ll i=cnt[1];i>=1;i--){
        for(ll rep=0;rep<behind[i]-pre;rep++){
            ans[pt]=0;
            pt--;
        }
        ans[pt]=1;
        pt--;
        pre=behind[i];
    }
    return ans;
    // return re;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80