Submission #761232

#	Time	Username	Problem	Language	Result	Execution time	Memory
761232		ksu2009en	Floppy (RMI20_floppy)	C++17	14.29 / 100	69 ms	5736 KiB

floppy

#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 (stderr)

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 / 7
• Subtask 2: 7.292570350799999 / 21
• Subtask 3: 0 / 72