oj.uz

Submission #761232

# Submission time Handle Problem Language Result Execution time Memory
761232 2023-06-19T11:31:45 Z ksu2009en Floppy (RMI20_floppy) C++17
14.2926 / 100
 69 ms 5736 KB 
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

#include "floppy.h"

string convert(ll n){
    string ans;
    ll mx = 0;
    
    for(int i = 17; i >= 0; i--)
        if((n >> i) % 2 != 0){
            mx = i;
            break;
        }
    
    for(int i = 0; i <= mx; i++){
        if((n >> i) % 2 != 0)
            ans += "1";
        else
            ans += "0";
    }
    reverse(ans.begin(), ans.end());
    
    return ans;
}

ll get(string a){
    ll ans = 0;
    
    ll p = 1;
    for(int i = a.size() - 1; i >= 0; i--){
        ans += (a[i] - '0') * p;
        
        p *= 2;
    }
    
    return ans;
}

string fill0(string a, ll n){
    reverse(a.begin(), a.end());
    
    ll c = n - a.size();
    for(int i = 0; i < c; i++)
        a += "0";
    
    reverse(a.begin(), a.end());
    return a;
}

void squize(vector<ll> &a){
    vector<ll> b = a;
    
    sort(b.begin(), b.end());
    
    map<ll, ll> mp;
    ll step = 0;
    
    for(auto i: b)
        if(!mp.count(i))
            mp[i] = step++;
    
    for(auto &i: a)
        i = mp[i];
}

void read_array(int subtask_id, const std::vector<int> &v) {
    vector<string>d;
    
    vector<ll>a;
    for(auto i: v)
        a.push_back(i);
    
    squize(a);
    
    for(auto i: a){
        d.push_back(convert(i));
    }
    
    for(auto &i: d)
        i = fill0(i, 15);

    
    string ans;
    for(auto i: d)
        ans += i;
    
    save_to_floppy(ans);
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    
    vector<ll> d;
    
    for(int i = 0; i < bits.size(); i += 15){
        string c;
        
        for(int j = i; j < i + 15; j++)
            c += bits[j];
        
        d.push_back(get(c));
    }
    
    vector<int>ans;
    
    for(int i = 0; i < a.size(); i++){
        ll mx = -1, pos = 0;
        
        for(int j = a[i]; j <= b[i]; j++){
            if(d[j] > mx){
                mx = d[j];
                pos = j;
            }
        }
        
        ans.push_back(pos);
    }

    return ans;
}
/*
 2
 4 1
 -2 -4 2 0
 0 1 0
 
 */

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i = 0; i < bits.size(); i += 15){
      |                    ~~^~~~~~~~~~~~~
floppy.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     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 2 ms 668 KB Output is correct
2 Correct 2 ms 660 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 2 ms 660 KB Output is correct
5 Correct 2 ms 672 KB Output is correct

Subtask #2
7.2925703508 / 21.0

# Verdict Execution time Memory Grader output
1 Partially correct 51 ms 4044 KB Partially correct
2 Partially correct 53 ms 4836 KB Partially correct
3 Partially correct 69 ms 4740 KB Partially correct
4 Partially correct 64 ms 4832 KB Partially correct
5 Partially correct 49 ms 4768 KB Partially correct

Subtask #3
0.0 / 72.0

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