oj.uz

Submission #634937

# Submission time Handle Problem Language Result Execution time Memory
634937 2022-08-25T09:11:30 Z danikoynov Floppy (RMI20_floppy) C++14
100 / 100
 457 ms 15164 KB 
#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;

const int maxn = 40010;
void save_to_floppy(const string &);
void read_array(int subtask_id, vector < int > const&v)
{
    stack < int > st;
    st.push(0);
    string bit = "";
    for (int i = 1; i < v.size(); i ++)
    {
        while(!st.empty() && v[st.top()] < v[i])
        {
            bit = bit + "0";
            st.pop();
        }
        st.push(i);
        bit = bit + "1";
    }
    save_to_floppy(bit);
}

vector < pair < int, int > > g[maxn];
int par[maxn];
int find_leader(int v)
{
    if (v == par[v])
        return v;
    return find_leader(par[v]);
}
void unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v < u)
        swap(v, u);
    par[u] = v;
}
vector < int > ans;
vector < int > solve_queries(int subtask_id, int N, const string &bits,
                             const vector < int > &a,
                             const vector < int > &b)
{

    for (int i = 0; i < N; i ++)
        par[i] = i;
        int m = a.size();
        ans.resize(m);
    for (int i = 0; i < m; i ++)
    {
        g[b[i]].push_back({a[i], i});
    }

    stack < int > st;
    st.push(0);
    int idx = 0;
    for (pair < int, int > p : g[0])
    {
        ans[p.second] = find_leader(p.first);
    }
    for (int i = 1; i < N; i ++)
    {
        while(bits[idx] != '1')
        {
            unite(st.top(), i);
            st.pop();
            idx ++;
        }
        st.push(i);
        idx ++;
        for (pair < int, int > p : g[i])
        {
            ans[p.second] = find_leader(p.first);
            ///cout << p.second << " : " << find_leader(p.first) << " " << p.first << " " << i << endl;
        }
    }

    /**for (int i = 0; i < m; i ++)
        cout << ans[i] << " ";
    cout << endl;*/
    return ans;

}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 1; i < v.size(); i ++)
      |                     ~~^~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:47:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |     for (int i = 0; i < N; i ++)
      |     ^~~
floppy.cpp:49:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   49 |         int m = a.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 3 ms 2732 KB Output is correct
2 Correct 3 ms 2724 KB Output is correct
3 Correct 2 ms 2732 KB Output is correct
4 Correct 3 ms 2724 KB Output is correct
5 Correct 4 ms 2612 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5644 KB Output is correct
2 Correct 36 ms 5548 KB Output is correct
3 Correct 27 ms 5544 KB Output is correct
4 Correct 39 ms 5580 KB Output is correct
5 Correct 35 ms 5660 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 15140 KB Output is correct
2 Correct 398 ms 15072 KB Output is correct
3 Correct 182 ms 15040 KB Output is correct
4 Correct 457 ms 15092 KB Output is correct
5 Correct 379 ms 15164 KB Output is correct