oj.uz

Submission #1056846

# Submission time Handle Problem Language Result Execution time Memory
1056846 2024-08-13T11:42:54 Z allin27x Floppy (RMI20_floppy) C++17
100 / 100
 67 ms 13412 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 40004;
int t[4*N];
int ar[N];
int n;
string ans="";


void build(int p, int l, int r){
	if (l==r){
		t[p] = l; return;
	}
	int m = (l+r)/2;
	build(2*p, l, m);
	build(2*p+1, m+1, r);
	t[p] = ar[t[2*p]] > ar[t[2*p+1]] ? t[2*p] : t[2*p+1];
}
void build(){build(1, 0, n-1);}

int query(int p, int tl, int tr, int l, int r){
	if (l>r) return -1;
	if (tl==l && tr==r) return t[p];
	int tm = (tl+tr)/2;
	int a = query(2*p, tl, tm, l, min(r,tm));
	int b = query(2*p+1, tm+1, tr, max(tm+1,l), r);
	if (a==-1 && b==-1) return -1;
	if (a==-1) return b;
	if (b==-1) return a;
	if (ar[a] > ar[b]) return a; else return b;
}
int query(int l, int r){return query(1,0,n-1,l,r);}


void save_to_floppy(const string &bits);

void encode(int l, int r){
	if (l==r){
		ans+="00"; return;
	}
	int m = query(l,r);
	if (m==l){
		ans += "01";
		encode(m+1, r);
	} else if (m==r){
		ans += "10";
		encode(l, m-1);
	} else {
		ans += "11";
		encode(l, m-1);
		encode(m+1, r);
	}
}
void read_array(int subt, const vector<int> &v){
	n = v.size(); for (int i=0; i<n; i++) ar[i] = v[i]; build();
	encode(0,n-1);
	save_to_floppy(ans);
}

int szl[N];
int szr[N];
int ind = 0;

void dfs(){
	int l = ans[2*ind]=='1'; char r = ans[2*ind+1]=='1';
	if (!l && !r) return;
	int old_ind = ind; ind+=1; dfs();
	if (!l){
		szr[old_ind] = ind-old_ind;
		return;
	}
	if (!r){
		szl[old_ind] = ind-old_ind;
		return;
	}
	szl[old_ind] = ind-old_ind;
	int old_ind1 = ind; ind+=1; dfs();
	szr[old_ind] = ind - old_ind1;
}

void decode(int i, int l, int r, int cd){
	if (l>r) return;
	if (l==r){
		ar[l] = cd; return;
	}
	int m = l + szl[i];
	ar[m] = cd;
	decode(i+1, l, m-1, cd-1);
	decode(i+1+szl[i], m+1, r, cd-1);
}

vector<int> solve_queries(int subt, int N, const string &bits, const vector<int> &a, const vector<int> &b){
	n = N;
	ans = bits;
	dfs();
	decode(0, 0, N-1, N);
	build();
	// for (int i=0; i<N; i++) cout<<szl[i]<<szr[i]<<'\n';
	vector<int> ans(a.size());
	for (int i=0; i<a.size(); i++){
		ans[i] = query(a[i],b[i]);
	}
	return ans;
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i=0; i<a.size(); 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 816 KB Output is correct
2 Correct 0 ms 808 KB Output is correct
3 Correct 0 ms 816 KB Output is correct
4 Correct 1 ms 808 KB Output is correct
5 Correct 0 ms 820 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2868 KB Output is correct
2 Correct 15 ms 2884 KB Output is correct
3 Correct 15 ms 3124 KB Output is correct
4 Correct 17 ms 3120 KB Output is correct
5 Correct 15 ms 2908 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9652 KB Output is correct
2 Correct 67 ms 9576 KB Output is correct
3 Correct 63 ms 10292 KB Output is correct
4 Correct 61 ms 13412 KB Output is correct
5 Correct 61 ms 12808 KB Output is correct