oj.uz

Submission #67298

# Submission time Handle Problem Language Result Execution time Memory
67298 2018-08-13T20:00:07 Z yusufake Hidden Sequence (info1cup18_hidden) C++14
100 / 100
 13 ms 588 KB 
#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,ans;
    int i,j,h,k,lim,zz,it;    
    lim = 3*n/4;
    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();
     }
    int kk = n-k;
    int t=0,tt=0;
    for(j=0;j<n;j++){
        vector < int > v;
        if(k + tt < kk + t){
            for(i=1;i<=tt+1;i++) v.pb(!h);
            for(i=1;i<=k;i++) v.pb(h);;
            if(isSubsequence(v)) { ans.pb(!h); tt++; kk--; }
            else { ans.pb(h); t++; k--; }
        }
        else{
            for(i=1;i<=t+1;i++) v.pb(h);
            for(i=1;i<=kk;i++) v.pb(!h);;
            if(isSubsequence(v)) { ans.pb(h); t++; k--; }
            else { ans.pb(!h); tt++; kk--; }
        }
    }
    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

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:38:17: warning: variable 'lim' set but not used [-Wunused-but-set-variable]
     int i,j,h,k,lim,zz,it;    
                 ^~~
hidden.cpp:38:21: warning: unused variable 'zz' [-Wunused-variable]
     int i,j,h,k,lim,zz,it;    
                     ^~
hidden.cpp:38:24: warning: unused variable 'it' [-Wunused-variable]
     int i,j,h,k,lim,zz,it;    
                        ^~
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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct: Maximum length of a query = 5
2 Correct 3 ms 436 KB Output is correct: Maximum length of a query = 6
3 Correct 2 ms 436 KB Output is correct: Maximum length of a query = 5
4 Correct 3 ms 452 KB Output is correct: Maximum length of a query = 5
5 Correct 2 ms 452 KB Output is correct: Maximum length of a query = 4

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is correct: Maximum length of a query = 83
2 Correct 9 ms 588 KB Output is correct: Maximum length of a query = 90
3 Correct 10 ms 588 KB Output is correct: Maximum length of a query = 96
4 Correct 6 ms 588 KB Output is correct: Maximum length of a query = 77
5 Correct 10 ms 588 KB Output is correct: Maximum length of a query = 95
6 Correct 6 ms 588 KB Output is correct: Maximum length of a query = 87
7 Correct 11 ms 588 KB Output is correct: Maximum length of a query = 97
8 Correct 7 ms 588 KB Output is correct: Maximum length of a query = 83
9 Correct 6 ms 588 KB Output is correct: Maximum length of a query = 101
10 Correct 8 ms 588 KB Output is correct: Maximum length of a query = 100
11 Correct 10 ms 588 KB Output is correct: Maximum length of a query = 96
12 Correct 13 ms 588 KB Output is correct: Maximum length of a query = 100
13 Correct 9 ms 588 KB Output is correct: Maximum length of a query = 101