oj.uz

Submission #856161

# Submission time Handle Problem Language Result Execution time Memory
856161 2023-10-02T18:18:03 Z gortomi Floppy (RMI20_floppy) C++17
100 / 100
 71 ms 13740 KB 
#include <stdlib.h>
#include <string.h>

#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
void read_array(int subtask_id, const vector<int> &v) {
    stack<int> s;
    int n = v.size();
    s.push(1e9 + 1);
    string bits = "";
    for(auto x : v)
    {
        while(s.top() < x)
        {
            s.pop();
            bits += '1';
        }
        bits += '0';
        s.push(x);
    }
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int N,
        const string &bits,
        const vector<int> &a, const vector<int> &b) {
    int m = a.size();
    vector<int> ans(m);
    vector<vector<pair<int, int> > > query(N);
    for(int i = 0; i < m; i++)
    {
        query[b[i]].push_back({a[i], i});
    }
    vector<int> c;
    int k = 0;
    for(int i = 0; i < N; i++)
    {
        while(bits[k] != '0')
        {
            c.pop_back();
            k++;
        }
        k++;
        c.push_back(i);
        for(auto [l, ind] : query[i])
        {
            ans[ind] = *lower_bound(c.begin(), c.end(), l);
        }
    }
    return ans;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:9:9: warning: unused variable 'n' [-Wunused-variable]
    9 |     int n = v.size();
      |         ^
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 1 ms 828 KB Output is correct
2 Correct 1 ms 828 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 2 ms 828 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 17 ms 3756 KB Output is correct
2 Correct 17 ms 4028 KB Output is correct
3 Correct 16 ms 4004 KB Output is correct
4 Correct 17 ms 4020 KB Output is correct
5 Correct 17 ms 3964 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 13740 KB Output is correct
2 Correct 71 ms 13388 KB Output is correct
3 Correct 68 ms 13528 KB Output is correct
4 Correct 69 ms 13632 KB Output is correct
5 Correct 66 ms 13632 KB Output is correct