Submission #857995

#	Time	Username	Problem	Language	Result	Execution time	Memory
857995		iulia_morariu	Floppy (RMI20_floppy)	C++17	28 / 100	29 ms	7968 KiB

floppy

#include <bits/stdc++.h>
#include <floppy.h>

using namespace std;

void read_array ( int subtask_id , const std :: vector<int> &v ){
    vector < pair<int, int> > v1;
    for(int i = 0; i < v.size(); i++){
        v1.push_back( {v[i], i} );
    }
    sort(v1.begin(), v1.end());

    int n = v.size();
/*
    cout << "v1 : " << endl;
    for(int i = 0; i < n; i++) cout << v1[i].first << " ";
    cout << endl;
    for(int i = 0; i < n; i++) cout << v1[i].second << " ";
    cout << endl;*/
    vector <string> b(v.size());
    for(int i = 0; i < n; i++){
        int i1 = i;
        while( i1 > 0 ){
            b[ v1[i].second ].push_back( char(i1 % 2 + '0') );
            i1 /= 2;
        }

        while(b[ v1[i].second ].size() < 14) b[ v1[i].second ].push_back('0');
    }
/*
    cout << "b : " << endl;
    for(int i = 0; i < n; i++){
        cout << b[i] << endl;
    }
*/
    string s1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < b[i].size(); j++) s1.push_back( b[i][j] );
    }
    save_to_floppy(s1);

  //  cout << "s1 = " << s1 << endl;

}

std::vector<int> solve_queries ( int subtask_id ,
int N, const std :: string &bits ,
const std :: vector<int> &a ,
const std :: vector<int> &b ){

    //cout << "bits : " << bits << endl;
    int n = N;
    int lg = log2(n) + 1;
    int rmq[n][lg];
    int p[n];
    int pt = 1;
    int it = 0;

    for(int i = 0; i < n; i++) p[i] = 0;
    for(int i = 0; i < bits.size(); i++){
        //cout << "it = " << it << " i = " << i << " p[it] = " << p[it] << endl;
        p[it] += pt * int(bits[i] - '0');
        pt *= 2;
        if( (i + 1) % 14 == 0 ){
            pt = 1;
            it++;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < lg; j++){
            rmq[i][j] = 0;
        }
    }

    for(int i = 0; i < n; i++){
        rmq[i][0] = i;
    }

    pt = 1;
    for(int j = 1; j < lg; j++){
        for(int i = 0; i + pt < n; i++){
            if( p[ rmq[i][j - 1] ] > p[ rmq[i + pt][j - 1] ] ){
                rmq[i][j] = rmq[i][j - 1];
            }else{
                rmq[i][j] = rmq[i + pt][j - 1];
            }
        }
        pt *= 2;
    }
/*
    cout << "rmq : " << endl;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < lg; j++) cout << rmq[i][j] << " ";
        cout << endl;
    }*/

    vector <int> sol;
    for(int i = 0; i < a.size(); i++){
        int l = min(a[i], b[i]), r = max(a[i], b[i]);
        int pmax = l;
        while(l <= r){
            int l1 = log2(r - l + 1);
            if( p[ rmq[l][l1] ] > p[pmax] ) pmax = rmq[l][l1];
            l += pow(2, l1);
        }
        sol.push_back(pmax);
    }

    return sol;


}

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:8:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
floppy.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 0; j < b[i].size(); j++) s1.push_back( b[i][j] );
      |                        ~~^~~~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < bits.size(); i++){
      |                    ~~^~~~~~~~~~~~~
floppy.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     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: 0 / 72