| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 642651 |
2022-09-20T10:07:14 Z |
TimDee |
Floppy (RMI20_floppy) |
C++17 |
|
64 ms |
8424 KB |
#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
void read_array(int subtask_id, const std::vector<int> &V) {
vector<int> v=V;
int n=v.size();
if (subtask_id!=3) {
vector<pair<int,int>> a(n);
for (int i=0; i<n; ++i) {
a[i]={v[i],i};
}
sort(a.begin(), a.end());
for (int i=0; i<n; ++i) {
v[a[i].second]=i;
}
int k=log2(n);
string s;
for (int i=0; i<n; ++i) {
string t;
for (int bit=k; bit>=0; --bit) {
t+=('0'+((v[i]>>bit)&1));
}
s+=t;
}
save_to_floppy(s);
} else {
string S;
vector<int> now;
vector<int> tmp;
v.push_back(-INT_MAX);
for (int i=0; i<n; ++i) now.push_back(i);
vector<int> ans;
vector<vector<int>> won(n);
while (now.size()>1) {
if (now.size()&1) now.push_back(n);
for (int i=0; i<now.size(); i+=2) {
int f=now[i],s=now[i+1];
if (v[f]>v[s]) {
if (s!=n) won[f].push_back(s);
S+='0';
tmp.push_back(f);
} else {
won[s].push_back(f);
S+='1';
tmp.push_back(s);
}
}
now=tmp;
tmp.clear();
}
ans.push_back(now[0]);
while (ans.size()<n) {
now.clear();
for (auto x:won[ans.back()]) {
now.push_back(x);
}
while (now.size()>1) {
if (now.size()&1) now.push_back(n);
for (int i=0; i<now.size(); i+=2) {
int f=now[i],s=now[i+1];
if (v[f]>v[s]) {
if (s!=n) won[f].push_back(s);
S+='0';
tmp.push_back(f);
} else {
won[s].push_back(f);
S+='1';
tmp.push_back(s);
}
}
now=tmp;
tmp.clear();
}
ans.push_back(now[0]);
}
save_to_floppy(S);
}
}
vector<int> t;
vector<int> A;
int sz=1, neutr;
int merge (int i, int j) {
if (A[i]>A[j]) return i;
else return j;
}
void update(int i, int l, int r) {
if (r-l==1) return;
int mid=(l+r)>>1;
update(2*i+1,l,mid);
update(2*i+2,mid,r);
t[i]=merge(t[2*i+1],t[2*i+2]);
}
int query(int i, int l, int r, int lx, int rx) {
if (l>=rx) return neutr;
if (r<=lx) return neutr;
if (l>=lx && r<=rx) return t[i];
int mid=(l+r)>>1;
int L=query(2*i+1,l,mid,lx,rx), R=query(2*i+2,mid,r,lx,rx);
return merge(L,R);
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
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 n=N,m=a.size();
int k=log2(n); while (sz<n) sz<<=1;
t.assign(2*sz-1,n);
string S=bits;
vector<int> v(n);
if (subtask_id!=3) {
for (int i=0; i<1ll*n*(k+1); i+=k+1) {
int x=0;
for (int bit=k; bit>=0; --bit) {
x+=((S[i+k-bit]=='1')<<bit);
}
v[i/(k+1)]=x;
}
} else {
int ptr=0;
vector<int> now;
vector<int> tmp;
for (int i=0; i<n; ++i) now.push_back(i);
vector<int> ans;
vector<vector<int>> won(n);
while (now.size()>1) {
if (now.size()&1) now.push_back(n);
for (int i=0; i<now.size(); i+=2) {
int f=now[i],s=now[i+1];
if (S[ptr++]=='0') {
if (s!=n) won[f].push_back(s);
tmp.push_back(f);
} else {
won[s].push_back(f);
tmp.push_back(s);
}
}
now=tmp;
tmp.clear();
}
ans.push_back(now[0]);
while (ans.size()<n) {
now.clear();
for (auto x:won[ans.back()]) {
now.push_back(x);
}
while (now.size()>1) {
if (now.size()&1) now.push_back(n);
for (int i=0; i<now.size(); i+=2) {
int f=now[i],s=now[i+1];
if (S[ptr++]=='0') {
if (s!=n) won[f].push_back(s);
tmp.push_back(f);
} else {
won[s].push_back(f);
tmp.push_back(s);
}
}
now=tmp;
tmp.clear();
}
ans.push_back(now[0]);
}
for (int i=0; i<n; ++i) {
v[ans[i]]=n-1-i;
}
}
neutr=n;
v.push_back(-INT_MAX);
A=v;
for (int i=0; i<n; ++i) t[sz-1+i]=i;
update(0,0,sz);
vector<int> ans(m,0);
for (int q=0; q<m; ++q) {
int l=a[q], r=b[q];
ans[q]=query(l,r+1);
}
return ans;
}
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i=0; i<now.size(); i+=2) {
| ~^~~~~~~~~~~
floppy.cpp:59:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | while (ans.size()<n) {
| ~~~~~~~~~~^~
floppy.cpp:66:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i=0; i<now.size(); i+=2) {
| ~^~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:146:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i=0; i<now.size(); i+=2) {
| ~^~~~~~~~~~~
floppy.cpp:161:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
161 | while (ans.size()<n) {
| ~~~~~~~~~~^~
floppy.cpp:168:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for (int i=0; i<now.size(); i+=2) {
| ~^~~~~~~~~~~
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 |
2 ms |
660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
668 KB |
Output is correct |
| 3 |
Correct |
2 ms |
668 KB |
Output is correct |
| 4 |
Correct |
2 ms |
660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
3568 KB |
Output is correct |
| 2 |
Correct |
37 ms |
3432 KB |
Output is correct |
| 3 |
Correct |
45 ms |
3460 KB |
Output is correct |
| 4 |
Correct |
35 ms |
3472 KB |
Output is correct |
| 5 |
Correct |
36 ms |
3572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
8424 KB |
L is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
