Submission #67110

#	Time	Username	Problem	Language	Result	Execution time	Memory
67110		yusufake	Hidden Sequence (info1cup18_hidden)	C++14	44 / 100	15 ms	764 KiB

hidden

#include<bits/stdc++.h>

#include "grader.h"

using namespace std;

#define mp make_pair
#define pb push_back
#define st first
#define nd second

typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;

const int mod = 1e9 + 7;
const int N   = 1e3 + 3;
/*
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;
}
*/
vector < int > findSequence (int n){
    vector < int > u;
    int i,j,h,k,lim,zz,it;    
    lim = n > 10 ? 3*n/4 : n/2;
    for(i=0;i<=n/2;i++){
        u.pb(1); 
        if(isSubsequence(u) == 0) break;
    }
    if(i <= n/2) { u.pop_back(); h = 1;  k=i;}
     else{
         h = 0;
         u.clear();
        for(k=0; ;k++){
            u.pb(0); 
            if(isSubsequence(u) == 0) break;
        }
         u.pop_back();
     }
    vector < int > ans = u;
     zz = 0;
    //cout << k << " ss\n";
    //exit(0);
    for(i=j=it=0;i<=k;i++,it++,j++){
        //cout << i << " " << j << " " << it << " uu\n";
        //if(i == 1) exit(0);
        for(; u.size() <= lim && isSubsequence(u); j++){
             u.insert(u.begin()+j , !h);
             ans.insert(ans.begin()+it++ , !h);
         }
       // for(auto x : u) cout << x << " "; puts("");
       if(isSubsequence(u)){  
           //cout << "wow";
             if(zz) assert(0); 
             zz = it; }
         else{
                 ans.erase(ans.begin()+--it);
             //it++;
        }
       // if(j == i+1)
        //cout << it << " it\n";
         for(; j > i ; ) u.erase(u.begin() + --j);
  //      exit(0);
    }

    if(zz){
        it = zz;
        for(; ans.size() < n ;) ans.insert(ans.begin() + it++ , !h);
    }    
    return ans;
}


/*
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");
        return 0;
    }
printf ("Ok, biggest queried length %d\n", maxQ);
return 0;
}
*/

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; u.size() <= lim && isSubsequence(u); j++){
               ~~~~~~~~~^~~~~~
hidden.cpp:82:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; ans.size() < n ;) ans.insert(ans.begin() + it++ , !h);
               ~~~~~~~~~~~^~~
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: 0 / 20
• Subtask 2: 44 / 80