Submission #1062974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062974		prvocislo	Floppy (RMI20_floppy)	C++17	7 / 100	23 ms	6076 KiB

floppy

// Guess who we ran into at the shops?
// Walking in circles like she was lost
// Didn't you hear?
// They called it all off

#include "floppy.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

struct solving
{
    struct sgt
    {
        vector<pair<int, int> > st;
        int n;
        void init(vector<int> v)
        {
            n = v.size();
            st.resize(v.size() * 2);
            for (int i = n; i < 2 * n; i++) st[i] = { v[i - n], i - n };
            for (int i = n - 1; i > 0; i--) st[i] = max(st[i * 2], st[i * 2 + 1]);
        }
        int query(int l, int r)
        {
            pair<int, int> p(-1, -1);
            for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
            {
                if (l & 1) p = max(p, st[l++]);
                if (r & 1) p = max(p, st[--r]);
            }
            return p.second;
        }
    };

    sgt s;
    int cnt = 0;
    string fl;
    void make(int l, int r)
    {
        if (r < l) return;
        int i = s.query(l, r), x = cnt;
        cnt += 2;
        if (l < i) fl[x] = '1', make(l, i - 1);
        if (r > i) fl[x + 1] = '1', make(i + 1, r);
    }

    void read_array(int subtask_id, const vector<int>& v)
    {
        s.init(v);
        fl.assign(v.size() * 2, '0');
        make(0, v.size() - 1);
        save_to_floppy(fl);
    }

    int tim = 0; // :) :wave:
    int val;
    vector<int> v2;
    int dfs(int u, const string& b)
    {
        int x = val, siz = 1; val--;
        if (b[u * 2] == '1') siz += dfs(u + 1, b);
        v2[tim++] = x;
        if (b[u * 2 + 1] == '1') siz += dfs(u + siz, b);
        return siz;
    }

    vector<int> solve_queries(int subtask_id, int n, const string& bits, const vector<int>& a, const vector<int>& b)
    {
        //if (n >= 5000) return vector<int>(a.size(), 0);
        val = n - 1;
        v2.resize(n, -1);
        dfs(0, bits);
        s.init(v2);
        vector<int> ans;
        for (int i = 0; i < a.size(); i++) ans.push_back(s.query(a[i], b[i]));
        return ans;
    }
};

void read_array(int subtask_id, const vector<int>& v)
{
    solving s;
    return s.read_array(subtask_id, v);
}
vector<int> solve_queries(int subtask_id, int n, const string& bits, const vector<int>& a, const vector<int>& b)
{
    solving s;
    return s.solve_queries(subtask_id, n, bits, a, b);
}

Compilation message (stderr)

floppy.cpp: In member function 'std::vector<int> solving::solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < a.size(); i++) ans.push_back(s.query(a[i], b[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: 0 / 21
• Subtask 3: 0 / 72