Submission #649981

#TimeUsernameProblemLanguageResultExecution timeMemory
649981dariaFloppy (RMI20_floppy)C++14
100 / 100
655 ms26376 KiB
#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(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(mx); bit[mx] += (id == l) ? '0' : '1'; bit[mx] += (id == r-1) ? '0' : '1'; ans += bit[mx]; if(id != l) dfs(v, l, id, mx); if(id != r-1) dfs(v, id+1, r, mx); } 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; dfs(v1, 0, n, -1); //cout << ans << endl; save_to_floppy(ans); } //------------------------------------------------------------------------------------------------- vector<int> ar; bool vis[F]; int nxt = 0; void rdfs(int id, int z, const string &s){ if(vis[id]) return; vis[id] = 1; if(s[2*id] == '1') rdfs(id+1, z+1, s); ar.push_back(z); if(s[2*id+1] == '1'){ while(vis[nxt]) nxt++; rdfs(nxt, z+1, s); } } 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<ar.size(); ++i) cout << ar[i] << " "; cout << endl; for(int i=0; i<N; ++i) st[F+i] = {ar[i], 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 (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...