Submission #62216

#	Time	Username	Problem	Language	Result	Execution time	Memory
62216		Benq	Hidden Sequence (info1cup18_hidden)	C++11	100 / 100	185 ms	568 KiB

hidden

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

// #define LOCAL 

#ifdef LOCAL 
bool isSubsequence (vector <int> v);
#else
#include "grader.h"
#endif

bool flip = 0;
int N, x, mxlen;
vi ans, done, num;

void trans(vi& x) { for (int& i: x) i ^= 1; }

bool get(vi v) { 
    if (flip) trans(v); 
    #ifdef LOCAL 
        F0R(i,sz(num)) {
            cout << " ";
            if (done[i]) cout << "[";
            else cout << '(';
            F0R(j,num[i]) cout << '1';
            if (done[i]) cout << ']';
            else cout << ')';
            cout << " ";
            if (i != sz(num)-1) cout << "0";
        }
        cout << "QUERY ";
        for (int i: v) cout << i << " ";
        cout << "\n";
    #endif
    return isSubsequence(v); 
}

vi mul(int x, int len) {
    vi v; F0R(i,len) v.pb(x);
    return v;
}

int getNum0() {
    int num = mxlen;
    while (num && !isSubsequence(mul(0,num))) num --;
    if (num == mxlen) {
        while (num && !isSubsequence(mul(1,num))) num --;
        num = N-num;
    }
    return num;
}

vi actual(vi v) {
    if (sz(v) == 0) return {};
    int nex[sz(v)+1][2];
    nex[sz(v)][0] = nex[sz(v)][1] = sz(v);
    F0Rd(i,sz(v)) {
        nex[i][0] = nex[i+1][0], nex[i][1] = nex[i+1][1];
        if (v[i] == 0) nex[i][0] = i;
        if (v[i] == 1) nex[i][1] = i;
    }
    vi ret = {0};
    int i = nex[0][0]+1;
    while (i < sz(v)) {
        if (nex[i][0] == sz(v)) i ++, ret.pb(1);
        else if (nex[i][1] == sz(v)) {
            if (ret.back() == 0) break;
            i ++, ret.pb(0);
        } else {
            if (nex[i][0] > nex[i][1]) i = nex[i][0]+1, ret.pb(0);
            else i = nex[i][1]+1, ret.pb(1);
        }
    }
    return ret;
}

bool allZero(vi v) {
    for (int i: v) if (i) return 0;
    return 1;
}

vi compress(vi v) {
    if (allZero(v)) return {};
    vi cur, ans;
    for (int i: v) {
        if (i == -1) {
            cur = actual(cur);
            ans.insert(ans.end(),all(cur));
            cur.clear();
        } else cur.pb(i);
    }
    cur = actual(cur);
    ans.insert(ans.end(),all(cur));
    return ans;
}

vi getRep(int pos) {
    vi t0;
    F0R(i,pos) {
        if (!done[i]) {
            if (num[i] == 0) t0.pb(-1);
            else t0.pb(1), t0.pb(1);
        } else F0R(j,num[i]) t0.pb(1);
        t0.pb(0);
    }
    t0 = compress(t0);
    
    vi v;
    F0R(i,num[pos]+1) v.pb(1);
    
    vi t1;
    FOR(i,pos+1,sz(num)) {
        t1.pb(0);
        if (!done[i]) {
            if (num[i] == 0) t1.pb(-1);
            else t1.pb(1), t1.pb(1);
        } else F0R(j,num[i]) t1.pb(1);
    }
    reverse(all(t1));
    t1 = compress(t1);
    reverse(all(t1));
    t0.insert(t0.end(),all(v));
    t0.insert(t0.end(),all(t1));
    return t0;
}

void dosmth() {
    vpi posi;
    F0R(i,x+1) if (!done[i]) {
        /*cout << "??\n";
        for (int j: getRep(i)) cout << j << " ";
        cout << "\n";
        cout << i << " " << sz(getRep(i)) << "\n";*/
        posi.pb({sz(getRep(i)),i});
    }
    sort(all(posi));
    if (posi[0].f > mxlen) {
        cout << "\nOOPS " << posi[0].s << "\n";
        for (int i: getRep(posi[0].s)) cout << i << " ";
        cout << "\n\n";
    }
    bool x = get(getRep(posi[0].s));
    // cout << posi[0].s << " " << x << " " << num[posi[0].s] << "\n";
    if (x) num[posi[0].s] ++;
    else done[posi[0].s] = 1;
}

vi findSequence (int n) {
    N = n, mxlen = N/2+1;
    x = getNum0();
    if (x > N/2) {
        flip = 1;
        x = N-x;
    }
    
    done.resize(x+1), num.resize(x+1);
    
    while (1) {
        int sum = x;
        vi bad; 
        F0R(i,x+1) {
            if (!done[i]) bad.pb(i);
            sum += num[i];
        }
        // cout << "OH " << sum << "\n";
        if (sum == N) break;
        if (sz(bad) == 1) {
            num[bad[0]] += N-sum;
            break;
        }
        dosmth();
    }
    F0R(i,x+1) {
        F0R(j,num[i]) ans.pb(1);
        if (i != x) ans.pb(0);
    }
    
    if (flip) trans(ans);
    return ans;
}

#ifdef LOCAL 
static int maxQ = 0;
static vector < int > theRealAnswer;

bool isSubsequence (vector < int > v) {
    if (v.size () > maxQ)
        maxQ = v.size ();
    int i = 0;
    for (auto it : v) {
        while (i < theRealAnswer.size () && it != theRealAnswer[i]) i ++;
        if (i == theRealAnswer.size ()) return 0;
        i ++;
    }
    return 1;
}

int main ()
{
int n, x;
scanf ("%d", &n), maxQ = 0;
for (int i=1; i<=n; i++)
    scanf ("%d", &x), theRealAnswer.push_back (x);

vector < int > ans = findSequence (n);
if (ans.size () != theRealAnswer.size ())
{
    printf ("Different lengths\n");
    for (auto it : ans)
        printf ("%d ", it);
    printf ("\n");
    return 0;
}

for (int i=0; i<ans.size (); i++)
    if (ans[i] != theRealAnswer[i])
    {
        printf ("WA position %d\n", i + 1);
        for (auto it : ans)
            printf ("%d ", it);
        printf ("\n");
        printf("Real: ");
        for (int j: theRealAnswer) printf("%d ",j);
        printf ("\n");
        return 0;
    }
printf ("Ok, biggest queried length %d\n", maxQ);
        for (int j: theRealAnswer) printf("%d ",j);
        printf ("\n");
return 0;
}
#else
#endif


/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~

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