Submission #398508

#	Time	Username	Problem	Language	Result	Execution time	Memory
398508		model_code	Floppy (RMI20_floppy)	C++17	59.27 / 100	168 ms	11548 KiB

floppy

/**
* user:  turevskii-2c9
* fname: Maxim
* lname: Turevskii
* task:  Floppy
* score: 64.0
* date:  2020-12-03 10:10:39.759270
*/
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
/*string o1;
void save_to_floppy(string bits)
{
    o1=bits;
}*/
void read_array(int id,const vector <int> &v)
{
    int n=v.size();
    vector <pair<int,int> > z1;
    for(int i=0;i<n;++i)
    {
        z1.push_back({v[i],i});
    }
    sort(z1.begin(),z1.end());
    vector <int> t(n);
    int curr=(-1);
    for(int i=0;i<z1.size();++i)
    {
        if(i==0 || z1[i].first!=z1[i-1].first)
        {
            ++curr;
            t[z1[i].second]=curr;
        }
        else
        {
            t[z1[i].second]=curr;
        }
    }
    int nxt[n];int prev[n];bool used[n];
    for(int i=0;i<n;++i)
    {
        nxt[i]=(i+1);prev[i]=(i-1);used[i]=false;
    }
    vector <int> h(n);
    vector <int> z;
    int cyc=(-1);
    int prev1[n],nxt1[n];
    vector <int> g;
    vector <int> f;
    for(int i=0;i<n;++i)
    {
        f.push_back(i);
    }
    vector <int> f1;
    while(true)
    {
        f1.clear();
        g.clear();
        ++cyc;
        int curr=0;
        if(used[curr])
        {
        z.clear();
        int o2=nxt[curr];
        z.clear();
        z.push_back(curr);
        while(true)
        {
            if(o2==n) break;
            if(!used[o2]) break;
            z.push_back(o2);
            o2=nxt[o2];
        }
        for(auto h1:z)
        {
            nxt[h1]=o2;
        }
        curr=o2;
        }
        if(curr==n) break;
        //cout<<curr<<" curr "<<endl;
        for(auto i:f)
        {
            if(i>=0 && i<n && !used[i]) {}
            else {continue;}
            //cout<<i<<" i "<<endl;
            int o1=prev[i];
            //cout<<o1<<" o1 "<<endl;
            z.clear();
            z.push_back(i);
            while(true)
            {
                if(o1==(-1)) break;
                if(!used[o1]) break;
                z.push_back(o1);
                o1=prev[o1];
            }
            for(auto h1:z)
            {
                prev[h1]=o1;
            }
            int o2=nxt[i];
            z.clear();
            z.push_back(i);
            while(true)
            {
                if(o2==n) break;
                if(!used[o2]) break;
                z.push_back(o2);
                o2=nxt[o2];
            }
            for(auto h1:z)
            {
                nxt[h1]=o2;
            }
            if((o1==(-1) || (t[o1]>=t[i] && !used[i])) && (o2==n || (t[o2]>=t[i] && !used[i])))
            {
                g.push_back(i);
                h[i]=cyc;
                prev1[i]=o1;nxt1[i]=o2;
            }
        }
        for(auto u:g)
        {
            int i=u;
            int o1=prev[i];
            //cout<<o1<<" o1 "<<endl;
            z.clear();
            z.push_back(i);
            while(true)
            {
                if(o1==(-1)) break;
                if(!used[o1]) break;
                z.push_back(o1);
                o1=prev[o1];
            }
            for(auto h1:z)
            {
                prev[h1]=o1;
            }
            int o2=nxt[i];
            z.clear();
            z.push_back(i);
            while(true)
            {
                if(o2==n) break;
                if(!used[o2]) break;
                z.push_back(o2);
                o2=nxt[o2];
            }
            for(auto h1:z)
            {
                nxt[h1]=o2;
            }
            f1.push_back(prev[u]);f1.push_back(nxt[u]);
            used[u]=true;
        }
        sort(f1.begin(),f1.end());
        f1.erase(unique(f1.begin(),f1.end()),f1.end());
        f=f1;
    }
    /*for(auto l:h)
    {
        cout<<l<<' ';
    }
    cout<<endl;*/
    string bits1,bits2;
    for(int i=0;i<n;++i)
    {
        if(h[i]==0) bits1+='1';
        else bits1+='0';
        //cout<<prev1[i]<<' '<<nxt1[i]<<endl;
        if(prev1[i]!=(-1) && h[prev1[i]]==(h[i]+1)) bits2+="10";
        else if(nxt1[i]!=n && h[nxt1[i]]==(h[i]+1)) bits2+="11";
        else bits2+="00";
    }
    bits1+=bits2;
    save_to_floppy(bits1);
}
const int maxn=40005;
pair <int,int> t[4*maxn];
pair <int,int> merg(pair <int,int> u,pair <int,int> v)
{
    if(u.first<=v.first)
    {
        return u;
    }
    else
    {
        return v;
    }
}
void to(int node,int tl,int tr,int pos,int val)
{
    if(tl>pos || tr<=pos)
    {
        return;
    }
    if((tr-tl)==1)
    {
        t[node]={-val,tl};
        return;
    }
    int tm=(tl+tr)/2;
    to(2*node+1,tl,tm,pos,val);to(2*node+2,tm,tr,pos,val);
    t[node]=merg(t[2*node+1],t[2*node+2]);
}
pair <int,int> get(int node,int tl,int tr,int l,int r)
{
    if(tl>=l && tr<=r)
    {
        return t[node];
    }
    if(tl>=r || tr<=l)
    {
        return {1e9,1e9};
    }
    int tm=(tl+tr)/2;
    return merg(get(2*node+1,tl,tm,l,r),get(2*node+2,tm,tr,l,r));
}
vector <int> solve_queries(int id,int n,const string &bits,const vector <int> &a,const vector <int> &b)
{
    vector <int> v;
    for(int i=0;i<n;++i)
    {
        if(bits[i]=='1') v.push_back(i);
    }
    int nxt[n];int prev[n];bool used[n];
    for(int i=0;i<n;++i)
    {
        nxt[i]=(i+1);prev[i]=(i-1);used[i]=false;
    }
    vector <int> v1;
    vector <int> z;
    vector <int> o(n);
    int cyc=(-1);
    while(!v.empty())
    {
        v1.clear();
        ++cyc;
        for(auto i:v)
        {
            o[i]=cyc;
            used[i]=true;
            if(bits[2*i+n]=='1' && bits[2*i+n+1]=='1')
            {
                int o2=nxt[i];
                z.clear();
                z.push_back(i);
                while(true)
                {
                if(o2==n) break;
                if(!used[o2]) break;
                z.push_back(o2);
                o2=nxt[o2];
               }
               for(auto h1:z)
               {
                nxt[h1]=o2;
               }
               if(o2!=n)
               v1.push_back(o2);
            }
            else if(bits[2*i+n]=='1' && bits[2*i+n+1]=='0')
            {
            int o1=prev[i];
            z.clear();
            z.push_back(i);
            while(true)
            {
                if(o1==(-1)) break;
                if(!used[o1]) break;
                z.push_back(o1);
                o1=prev[o1];
            }
            for(auto h1:z)
            {
                prev[h1]=o1;
            }
            if(o1!=(-1))
            v1.push_back(o1);
            }
            else {}
        }
        sort(v1.begin(),v1.end());
        v1.erase(unique(v1.begin(),v1.end()),v1.end());
        v=v1;
    }
    for(int i=0;i<o.size();++i)
    {
        to(0,0,maxn,i,o[i]);
    }
    //cout<<get(0,0,maxn,0,1).first<<' '<<get(0,0,maxn,0,1).second<<" get "<<endl;
    /*for(auto l:o)
    {
        cout<<l<<' ';
    }
    cout<<endl;*/
    vector <int> res(a.size());
    for(int i=0;i<a.size();++i)
    {
        int l=a[i];
        int r=b[i];
        pair <int,int> u=get(0,0,maxn,l,r+1);
        res[i]=u.second;
    }
    return res;
}
/*int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    read_array(0,{1,2,3,6,6,5,2,3,5,6});
    //vector <int> a={0,1},b={5,6};
    //vector <int> res=solve_queries(0,9,o1,a,b);
    //for(auto h:res) cout<<h<<' ';
    return 0;
}*/

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<z1.size();++i)
      |                 ~^~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:290:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  290 |     for(int i=0;i<o.size();++i)
      |                 ~^~~~~~~~~
floppy.cpp:301:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  301 |     for(int i=0;i<a.size();++i)
      |                 ~^~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 31.267123214399998 / 72