| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 855976 |
2023-10-02T13:16:56 Z |
mraron |
Floppy (RMI20_floppy) |
C++17 |
|
555 ms |
67932 KB |
#include <stdlib.h>
#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define xx first
#define yy second
deque<char> merge(deque<char>& a, deque<char>& b) {
if(sz(b)>sz(a)) {
while(!a.empty()) {b.push_front(a.back()); a.pop_back();}
return b;
}else {
while(!b.empty()) {a.push_back(b.front()); b.pop_front();}
return a;
}
}
deque<char> construct(int L, int R, set<pair<int,int>>& ord, const vector<int>& t) {
if(L>R) return {};
int mid=(L+R)/2;
int biggestPos=prev(ord.end())->yy;
ord.erase({t[biggestPos], biggestPos});
deque<char> a,b;
if(biggestPos<=mid) {
for(int i=L;i<biggestPos;++i) {
ord.erase({t[i], i});
}
b=construct(biggestPos+1, R, ord, t);
for(int i=L;i<biggestPos;++i) {
ord.insert({t[i], i});
}
a=construct(L, biggestPos-1, ord, t);
}else {
for(int i=biggestPos+1;i<=R;++i) {
ord.erase({t[i], i});
}
a=construct(L, biggestPos-1, ord, t);
for(int i=biggestPos+1;i<=R;++i) {
ord.insert({t[i], i});
}
b=construct(biggestPos+1, R, ord, t);
}
deque<char> res;
if(a.empty()) res.push_back('0'); else res.push_back('1');
if(b.empty()) res.push_back('0'); else res.push_back('1');
a=merge(a,b);
return merge(res, a);
}
void read_array(int subtask_id, const std::vector<int> &v) {
set<pair<int,int>> ord;
for(int i=0;i<sz(v);++i) ord.insert({v[i], i});
deque<char> b=construct(0, sz(v)-1, ord, v);
string bits;
for(auto i:b) bits.push_back(i);
save_to_floppy(bits);
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
int ind=0;
vector<int> par(N, -1), lvl(N, 0);
function<pair<int,int>(int, int)> dfs=[&](int pos, int l) -> pair<int,int> {
int st=pos+2, bal=-1, x, jobb=-1;
if(bits[pos]=='1') {
auto res=dfs(st, l+1);
st=res.xx;
bal=res.yy;
}
x=ind++;
lvl[x]=l;
//~ cerr<<x<<" "<<pos<<" "<<l<<" "<<bits<<"\n";
if(bits[pos+1]=='1') {
auto res=dfs(st, l+1);
st=res.xx;
jobb=res.yy;
}
if(bal!=-1) par[bal]=x;
if(jobb!=-1) par[jobb]=x;
return {st, x};
};
dfs(0, 0);
//~ for(auto i:par) cerr<<i<<" ";
//~ cerr<<"\n";
vector<array<int,17>> dp(N);
for(int i=0;i<N;++i) dp[i][0]=par[i];
for(int j=1;j<17;++j) {
for(int i=0;i<N;++i) {
dp[i][j]=(dp[i][j-1]==-1?-1:dp[dp[i][j-1]][j-1]);
}
}
vector<int> ans(sz(a));
for(int i=0;i<sz(a);++i) {
int x=a[i], y=b[i];
if(lvl[x]>lvl[y]) swap(x,y);
for(int j=16;j>=0;j--) {
int q=dp[y][j];
if(q!=-1 && lvl[q]>=lvl[x]) y=q;
}
if(x==y) {
ans[i]=x;
continue ;
}
for(int j=16;j>=0;j--) {
int p=dp[x][j], q=dp[y][j];
if(p!=q) x=p, y=q;
}
ans[i]=dp[x][0];
}
return ans;
}
Compilation message
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 |
Correct |
1 ms |
804 KB |
Output is correct |
| 2 |
Correct |
1 ms |
820 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1084 KB |
Output is correct |
| 5 |
Correct |
1 ms |
820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
3628 KB |
Output is correct |
| 2 |
Correct |
30 ms |
4500 KB |
Output is correct |
| 3 |
Correct |
45 ms |
17708 KB |
Output is correct |
| 4 |
Correct |
37 ms |
10572 KB |
Output is correct |
| 5 |
Correct |
32 ms |
4528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
12420 KB |
Output is correct |
| 2 |
Correct |
132 ms |
14436 KB |
Output is correct |
| 3 |
Correct |
555 ms |
67932 KB |
Output is correct |
| 4 |
Correct |
252 ms |
40292 KB |
Output is correct |
| 5 |
Correct |
128 ms |
14432 KB |
Output is correct |
