Submission #130267

#	Time	Username	Problem	Language	Result	Execution time	Memory
130267		nikolapesic2802	Hidden Sequence (info1cup18_hidden)	C++14	59 / 100	9 ms	420 KiB

hidden

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

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}

bool isSubsequence(vector<int> v);
vector<int> findSequence(int n)
{
    int lim=n/2+1;
    vector<int> num(2,-1);
    for(int i=1;i<=lim;i++)
    {
        vector<int> a;
        for(int j=0;j<i;j++)
            a.pb({0});
        if(!isSubsequence(a))
        {
            num[0]=i-1;
            num[1]=n-i+1;
            break;
        }
    }
    if(num[0]==-1)
    {
        for(int i=1;i<=lim;i++)
        {
            vector<int> a;
            for(int j=0;j<i;j++)
                a.pb({1});
            if(!isSubsequence(a))
            {
                num[1]=i-1;
                num[0]=n-i+1;
                break;
            }
        }
    }
    assert(num[0]!=-1);
    int a=0,b=1;
    if(num[a]>num[b])
        swap(a,b);
    vector<int> positions;
    for(int i=0;i<=num[a];i++)
    {
        vector<int> q;
        for(int j=0;j<i;j++)
            q.pb(a);
        q.pb(b);
        for(int j=i;j<num[a];j++)
            q.pb(a);
        if(isSubsequence(q))
            positions.pb(i);
    }
    vector<pair<int,int> > seq;
    int last=0;
    for(auto p:positions)
    {
        if(p!=last)
            seq.pb({a,p-last});
        last=p;
        seq.pb({b,1});
    }
    if(last!=num[a])
        seq.pb({a,num[a]-last});
    if(positions.size()>1)
    {
        if(positions.size()!=num[b])
        {
            int limit=(num[b]-positions.size()+2)/2,m=seq.size(),sum=0;
            if((num[b]-positions.size()+2)&1)
                limit++;
            for(int i=0;i<m;i++)
            {
                if(seq[i].f==a)
                    continue;
                seq[i].s=-1;
                for(int j=2;j<=limit;j++)
                {
                    int poc=1,kraj=m-1;
                    if(i==0)
                        poc=0;
                    if(i==m-1)
                        kraj=m;
                    vector<int> q;
                    for(int k=poc;k<kraj;k++)
                    {
                        if(k==i)
                            for(int l=0;l<j;l++)
                                q.pb(b);
                        else
                            q.pb(seq[k].f);
                    }
                    if(!isSubsequence(q))
                    {
                        seq[i].s=j-1;
                        sum+=j-1;
                        break;
                    }
                }
            }
            int cnt=0;
            for(int i=0;i<m;i++)
                if(seq[i].s==-1)
                    cnt++;
            if(cnt>1)
            {
                for(int i=0;i<m;i++)
                    if(seq[i].s==-1)
                        seq[i].s=limit;
            }
            else
                for(int i=0;i<m;i++)
                    if(seq[i].s==-1)
                        seq[i].s=num[b]-sum;
        }
    }
    else
        for(auto &p:seq)
            if(p.f==b)
                p.s=num[b];
    vector<int> sol;
    for(auto p:seq)
        for(int i=0;i<p.s;i++)
            sol.pb(p.f);
    return sol;
}

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:88:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(positions.size()!=num[b])
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: 15 / 20
• Subtask 2: 44 / 80