Submission #859701

#	Time	Username	Problem	Language	Result	Execution time	Memory
859701		activedeltorre	Floppy (RMI20_floppy)	C++14	82.36 / 100	368 ms	10876 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
//#include "floppy.h"

#include "floppy.h"
/*
#define NMAX 100000
#define MMAX 100000

int subtask_id, N, M;
std::vector<int> v, sorted_v;
std::vector<int> a, b;
std::vector<int> correct_answers;
// Print score to stdout and exit.
void score_and_exit(const double pts, const char *verdict) {
    cout<<verdict;
    cout<<endl<<pts;
    exit(0);
}

// Contestant sent too many bits.
void too_many_bits() {
    score_and_exit(0, "Too many stored bits!");
}

// Contestant did not send any bits.
void misformatted_stored_bits() {
    score_and_exit(0, "Misformatted stored bits or save_to_floppy not called!");
}

// Contestant did not call the answer function.
void answer_not_provided() {
    score_and_exit(0, "Answer not provided!");
}

// Contestant sent a wrong answer.
void wrong_answer() {
    score_and_exit(0, "Wrong answer to query!");
}

// Contestant sent a correct answer.
void correct_answer() {
    score_and_exit(1, "OK!");
}*/
using namespace std;
vector<int>ans;
stack<int>st2;
int par[40005];
string biti;
vector<int>vec;
stack<int>st;
vector<int> solve_queries(int subtask_id, int N,const string &bits,const vector<int> &a, const vector<int> &b)
{
    int n,q,i,aux,j,poz;
    n=N;
    q=a.size();
    poz=1;
    for(i=1;i<=n;i++)
    {
        par[i]=0;
    }
    for(i=1;i<=n;i++)
    {
        int cnt=0,iter=0,val=0,sum=0;
        while(bits[poz]=='1')
        {
            poz++;
            cnt++;
        }
        if(cnt==1)
        {
            val=1;
            iter=1;
        }
        if(cnt==2)
        {
            val=3;
            iter=1;
        }
        if(cnt==3)
        {
            val=5;
            iter=2;
        }
        if(cnt==4)
        {
            val=0;
            iter=5;
        }
        if(cnt==5)
        {
            iter=17;
            val=0;
        }
        sum=0;
        for(j=1;j<=iter;j++)
        {
            poz++;
            sum=sum*2+bits[poz]-'0';
        }
        sum+=val;
        for(j=1;j<=sum;j++)
        {
            par[st2.top()]=i;
            st2.pop();
        }
        st2.push(i);
        poz++;
    }
    int l,r;
    for(i=0;i<q;i++)
    {
        if(bits[0]=='0')
        {
            l=n+1-(b[i]+1);
            r=n+1-(a[i]+1);
        }
        else
        {
            l=a[i]+1;
            r=b[i]+1;
        }
        for(j=l;j<=r;j++)
        {
            if(par[j]>r || par[j]==0)
            {
                if(bits[0]=='1')
                ans.push_back(j-1);
                else
                ans.push_back(n-j);
                break;
            }
        }
    }
    return ans;
}

/*
void read_test() {
    cin>>subtask_id;
    cin>>N>>M;
    assert(1 <= N && N <= NMAX);
    assert(0 <= M && M <= MMAX);
    v.resize(N);
    for (int i = 0; i < N; ++i) {
        assert(scanf("%d", &v[i]) == 1);
    }

    // Check all values are distinct.
    sorted_v.resize(N);
    for (int i = 0; i < N; ++i) {
        sorted_v[i] = v[i];
    }
    std::sort(sorted_v.begin(), sorted_v.end());
    for (int i = 0; i + 1 < N; ++i) {
        assert(sorted_v[i] < sorted_v[i + 1]);
    }

    a.resize(M);
    b.resize(M);
    correct_answers.resize(M);
    for (int i = 0; i < M; ++i) {
        assert(scanf("%d%d%d", &a[i], &b[i], &correct_answers[i]) == 3);
        assert(0 <= a[i] && a[i] <= correct_answers[i] &&
              correct_answers[i] <= b[i] && b[i] < N);
    }
}

void save_to_floppy(const std::string &bits) {
    std::vector<int> contestant_answers = solve_queries(subtask_id, N, bits, a, b);
    for (int i = 0; i < M; ++i) {
        if (contestant_answers[i] != correct_answers[i]) {
            wrong_answer();
        }
    }
    correct_answer();
    exit(0);
}*/
void read_array(int subtask_id, const vector<int> &v)
{
    int n=v.size(),i;
    int cnt=0;
    for(i=0;i<n;i++)
    {
        if(v[i]>v[i-1])
        {
            cnt++;
        }
        vec.push_back(v[i]);
    }
    biti.push_back('1');
    st.push(1e9);
    for(i=0;i<n;i++)
    {
        cnt=0;
        while(st.top()<vec[i])
        {
            st.pop();
            cnt++;
        }
        st.push(vec[i]);
        if(cnt==0)
        {
            biti.push_back('0');
        }
        else if(cnt<=2)
        {
            biti.push_back('1');
            biti.push_back('0');
            biti.push_back('0'+cnt-1);
        }
        else if(cnt<=4)
        {
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('0');
            biti.push_back('0'+cnt-3);
        }
        else if(cnt<=8)
        {
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('0');
            cnt=cnt-5;
            biti.push_back('0'+cnt/2);
            biti.push_back('0'+cnt%2);
        }
        else if(cnt<=31)
        {
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('0');
            int pow=16;
            for(pow;pow>=1;pow=pow/2)
            {
                biti.push_back('0'+cnt/pow);
                cnt=cnt%pow;
            }
        }
        else
        {
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('1');
            biti.push_back('0');
            int pow=65536;
            for(pow;pow>=1;pow=pow/2)
            {
                biti.push_back('0'+cnt/pow);
                cnt=cnt%pow;
            }
        }
    }
    save_to_floppy(biti);
}
/*
int main(int argc, char **argv) {
    // Read input data.
    read_test();

    // Send subtask_id, v.
    read_array(subtask_id, v);

    answer_not_provided();
    return 0;
}*/

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:63:15: warning: unused variable 'aux' [-Wunused-variable]
   63 |     int n,q,i,aux,j,poz;
      |               ^~~
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:246:17: warning: statement has no effect [-Wunused-value]
  246 |             for(pow;pow>=1;pow=pow/2)
      |                 ^~~
floppy.cpp:261:17: warning: statement has no effect [-Wunused-value]
  261 |             for(pow;pow>=1;pow=pow/2)
      |                 ^~~
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: 54.354962894399996 / 72