제출 #1218432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218432		damamila	Floppy (RMI20_floppy)	C++20	7 / 100	1117 ms	3824 KiB

floppy

#include <bits/stdc++.h>

using namespace std;

//~ #define int long long

string str;
int nxt = 0;

void save_to_floppy(const string &bits);

//~ void save_to_floppy(const string &bits) {
	//~ return;
//~ }

void rek1(vector<int> curr) {
	if (curr.size() < 2) return;
	pair<int, int> ans = {curr[0], 0};
	for (int i = 1; i < (int)curr.size(); i++) {
		if (curr[i] > ans.first) ans = {curr[i], i};
	}
	for (int i = 0; i < (int)curr.size(); i++) {
		if (ans.second == i) str.push_back('1');
		else str.push_back('0');
	}
	vector<int> tmp;
	for (int i = 0; i < ans.second; i++) tmp.push_back(curr[i]);
	rek1(tmp);
	tmp.clear();
	for (int i = ans.second+1; i < (int)curr.size(); i++) tmp.push_back(curr[i]);
	rek1(tmp);
}

void read_array(int subtask_id, const vector<int> &v) {
	rek1(v);
	//~ cout << str << endl;
	save_to_floppy(str);
}

int rek2(int l, int r, int lb, int rb, int tmp) { //tmp to correct inidices
	//~ cout << l << " " << r << " " << lb << " " << rb << " " << tmp << " " << nxt << " " << endl;
	if (rb < lb) return -1;
	if (lb == rb) return lb+tmp; //used to have an additional check here
	int idx = 0;
	for (int i = lb+nxt; i <= rb+nxt; i++) {
		if (str[i] == '1') idx = i-nxt;
	}
	//~ cout << idx << endl;
	if (idx+tmp >= l && idx+tmp <= r) return idx+tmp;
	nxt += rb+1;
	if (l < idx+tmp) return rek2(l, r, 0, idx-1, lb+tmp);
	else rek2(l, r, 0, idx-1, lb+tmp);
	return rek2(l, r, 0, rb-idx-1, lb+idx+1+tmp);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
	vector<int> ans;
	str = bits;
	for (int q = 0; q < (int)a.size(); q++) {
		nxt = 0;
		ans.push_back(rek2(a[q], b[q], 0, N-1, 0));
		//~ cout << "JA " << ans.back() << endl;
	}
	//~ for (int i : ans) cout << i << " ";
	return ans;
}

//~ signed main() {
	//~ read_array(3, {1, 3, 2, 4, 6, 5, 9});
	//~ vector<int> a = {0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6};
	//~ vector<int> b = {0, 1, 4, 6, 1, 2, 6, 2, 3, 3, 5, 5, 6};
	//~ solve_queries(3, 7, str, a, b);
//~ }

• Subtask 1: 7 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72