| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 649748 |
2022-10-11T10:17:05 Z |
daria |
Floppy (RMI20_floppy) |
C++14 |
|
118 ms |
20144 KB |
#include "bits/stdc++.h"
#include "floppy.h"
using namespace std;
const int F = (1 << 16);
int n;
string ans;
vector<string> bit(F, "");
vector<int> adj[F];
void dfs(int s){
ans += bit[s];
for(auto u : adj[s]) dfs(u);
}
void solve(const vector<int> &v, int l, int r, int p){
int mx = -1, id = -1;
for(int i=l; i<r; ++i)
if(v[i] > mx){ mx = v[i]; id = i;}
if(p != -1) adj[p].push_back(v[id]);
if(id == l) bit[v[id]] += '0';
else bit[v[id]] += '1';
if(id == r-1) bit[v[id]] += '0';
else bit[v[id]] += '1';
if(id != l) solve(v, l, id, v[id]);
if(id != r-1) solve(v, id+1, r, v[id]);
}
void read_array(int subtask_id, const std::vector<int> &v) {
n = v.size();
vector<pair<int, int> > v0(n);
for(int i=0; i<n; ++i) v0[i] = {v[i], i};
sort(v0.begin(), v0.end());
vector<int> v1(n);
for(int i=0; i<n; ++i) v1[v0[i].second] = i;
solve(v1, 0, n, -1);
dfs(n-1);
//cout << ans << endl;
save_to_floppy(ans);
}
//-------------------------------------------------------------------------------------------------
vector<int> sz(F, 1), l(F, 0), val(F, 0);
bool vis[F];
int nxt = 0;
void rdfs(int id, int z, const string &s){
//cout << id << endl;
if(vis[id]) return;
vis[id] = 1;
val[id] = z;
if(s[2*id] == '1'){
l[id+1] += l[id];
//cout << "+ l padre: " << id+1 << " " << l[id+1] << endl;
rdfs(id+1, z+1, s);
sz[id] += sz[id+1];
l[id] += sz[id+1];
//cout << "+ sz figlio sx: " <<id << " " << l[id] << endl;
}
if(s[2*id+1] == '1'){
while(vis[nxt]) nxt++;
l[nxt] += l[id] + 1;
rdfs(nxt, z+1, s);
sz[id] += sz[nxt];
//cout << "+ l padre + 1: " << nxt << " " << l[nxt] << endl;
}
}
vector<pair<int, int> > st(2*F, {F, -1});
pair<int, int> query(int v, int tl, int tr, int l, int r){
if(r <= tl || tr <= l) return {F, -1};
if(l <= tl && tr <= r) return st[v];
int tm = (tl +tr)/2;
return min(query(2*v, tl, tm, l, r), query(2*v+1, tm, tr, l , r));
}
std::vector<int> solve_queries(int subtask_id, int N, const std::string &s,
const std::vector<int> &a, const std::vector<int> &b) {
rdfs(0, 0, s);
for(int i=0; i<N; ++i) st[F+l[i]] = {val[i], l[i]};
for(int i=F-1; i>0; --i) st[i] = min(st[2*i], st[2*i+1]);
vector<int> res;
for(int i=0; i<a.size(); ++i) res.push_back(query(1, 0, F, a[i], b[i]+1).second);
res.resize(a.size());
return res;
}
// l = sz(figlio sinistro) + l(padre) + (é figlio destro?)
//1223200
//1202312
//1202312
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:91:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0; i<a.size(); ++i) res.push_back(query(1, 0, F, a[i], b[i]+1).second);
| ~^~~~~~~~~
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
13532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
20144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
