Submission #401508

#	Time	Username	Problem	Language	Result	Execution time	Memory
401508		Drew_	Floppy (RMI20_floppy)	C++14	100 / 100	123 ms	10496 KiB

floppy

#include <stdlib.h>
#include <string.h>

#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

void read_array(int subtask_id, const std::vector<int> &v) {
	vector<int> st;
	string s;
    for (int i = 0; i < (int)v.size(); ++i)
    {
    	while (!st.empty() && st.back() < v[i])
    		s.pb('0'), st.pop_back();
    	s.pb('1'); st.pb(v[i]);
    }
    //cerr << "s: " << s << '\n';
    save_to_floppy(s);
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
	const int MAX = 4e4 + 7;
	const int LG = (int)log2(MAX);

	int up[MAX][LG];

	vector<int> st;
	for (int i = 0, num = 0; i < (int)bits.size(); ++i)
	{
		if (bits[i] == '0')
			st.pop_back();
		else
		{
			if (st.empty()) up[num][0] = num;
			else up[num][0] = st.back();
			st.pb(num++);
		}
	}

	//for (int i = 0; i < N; ++i)
	//	cerr << i << ": " << up[i][0] << '\n';

	for (int j = 1; j < LG; ++j)
		for (int i = 0; i < N; ++i)
			up[i][j] = up[up[i][j-1]][j-1];

	vector<int> answers;
	for (int i = 0; i < (int) a.size(); ++i)
	{
		int l = a[i], r = b[i];
		for (int j = LG-1; j >= 0; --j)
			if (up[r][j] >= l)
				r = up[r][j];
		answers.pb(r);
	}

    return answers;
}

Compilation message (stderr)

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