oj.uz

답안 #646749

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646749 2022-09-30T14:37:40 Z TwoFourFive Floppy (RMI20_floppy) C++14
0 / 100
 768 ms 327680 KB 
#include <stdlib.h>
#include <string.h>

#include "floppy.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef vector<ll> vl;
const ll INF = 100005, LONGBOI = 100000000005, BITSMAX = 16;

ll maxpos=0;
map<ll, ll> mp;

string ToStr(ll x){
    string ans="";
    for(int i=BITSMAX-1; i >= 0; i--){
        ans += '0' + ((x>>i)&1);
    }
    return ans;
}

ll FromStr(string s){
    ll x = 0;
    for(int i=0; i < BITSMAX; i++){
        x <<= 1;
        x += s[i]-'0';
    }
    return x;
}

void BuildTree(ll we, ll l, ll r, vl &t, vl &a){
    maxpos = max(maxpos, we);
    if(l == r) { t[we] = a[l]; return; }
    ll tm = (l+r)/2;
    BuildTree(2*we+1, l, tm, t, a);
    BuildTree(2*we+2, tm+1, r, t, a);
    t[we] = max(t[2*we+1], t[2*we+2]);
    return;
}

ll GetMax(ll we, ll l, ll r, ll tl, ll tr, vl &t){
    if(l > tr || r < tl) return -LONGBOI;
    if(tl <= l && r <= tr) return t[we];

    ll tm = (l+r)/2;
    return max(GetMax(2*we+1, l, tm, tl, tr, t), GetMax(2*we+2, tm+1, r, tl, tr, t));
}

void read_array(int subtask_id, const vector<int> &v) {
    vl vec;
    map<ll, ll> newNums;
    ll n = v.size();
    for(auto x : v) { vec.push_back(x); }
    sort(vec.begin(), vec.end());
    for(auto x : vec){
        if(newNums.count(x) == false){
            newNums[x] = newNums.size();
        }
    }
    vl t(4*(n+5));
    vl a(n+5);
    for(int i=0; i < n; i++) { a[i+1] = newNums[v[i]]; mp[a[i+1]] = i; }
    for(int i=1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
    cout << "map" << endl;
    for(auto x : mp) { cout << x.first << " " << x.second << endl; }
    cout << endl;
    BuildTree(0, 1, n, t, a);
    string bits = "";
    for(int i=0; i <= maxpos; i++) { cout << "i = " << i << " t[i] = " << t[i] << endl; }
    for(int i=0; i <= maxpos; i++) { bits += ToStr(t[i]); cout << bits << " " << ToStr(t[i]) << endl; }
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
    vl t(4*(N+5));
    for(auto x : a) cout << x << " ";
    cout << endl;
    for(auto x : b) cout << x << " ";
    cout << endl;
    for(int i=0; i <= maxpos; i++) { t[i] = FromStr(bits.substr(i*BITSMAX, (i+1)*BITSMAX)); cout << i*BITSMAX << " " << (i+1)*BITSMAX << endl; }
    for(int i=0; i <= maxpos; i++) { cout << "i = " << i << " t[i] = " << t[i] << endl; }

    vl ans;
    ll m  = a.size();
    for(int i=0; i < m; i++){
        cout << GetMax(0, 1, N, a[i]+1, b[i]+1, t) << endl;
        ans.push_back(mp[GetMax(0, 1, N, a[i]+1, b[i]+1, t)]);
    }
    for(auto x : ans) cout << x << " ";
    cout << endl;

    //vl ans = {0, 0, 0, 0, 1, 2, 2, 2, 2, 3};
    return ans;
}

Compilation message

floppy.cpp:10:34: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '100000000005' to '1215752197' [-Woverflow]
   10 | const ll INF = 100005, LONGBOI = 100000000005, BITSMAX = 16;
      |                                  ^~~~~~~~~~~~
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
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 17564 KB Invalid run index for stub.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 555 ms 327680 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 768 ms 327680 KB Memory limit exceeded
2 Halted 0 ms 0 KB -