oj.uz

Submission #857995

# Submission time Handle Problem Language Result Execution time Memory
857995 2023-10-07T09:20:48 Z iulia_morariu Floppy (RMI20_floppy) C++17
28 / 100
 29 ms 7968 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 828 KB Output is correct
2 Correct 2 ms 984 KB Output is correct
3 Correct 2 ms 824 KB Output is correct
4 Correct 2 ms 832 KB Output is correct
5 Correct 2 ms 828 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5072 KB Output is correct
2 Correct 27 ms 4968 KB Output is correct
3 Correct 28 ms 5092 KB Output is correct
4 Correct 27 ms 5036 KB Output is correct
5 Correct 29 ms 5088 KB Output is correct

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 7968 KB L is too large
2 Halted 0 ms 0 KB -