Submission #634937

#	Time	Username	Problem	Language	Result	Execution time	Memory
634937		danikoynov	Floppy (RMI20_floppy)	C++14	100 / 100	457 ms	15164 KiB

floppy

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

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