| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1062859 |
2024-08-17T11:19:45 Z |
TimDee |
Floppy (RMI20_floppy) |
C++17 |
|
64 ms |
15744 KB |
// Guess who we ran into at the shops?
// Walking in circles like she was lost
// Didn't you hear?
// They called it all off
#include "floppy.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
struct sgt
{
vector<pair<int, int> > st;
int n;
void init(vector<int> v)
{
n = v.size();
st.resize(v.size() * 2);
for (int i = n; i < 2 * n; i++) st[i] = { v[i - n], i - n };
for (int i = n - 1; i > 0; i--) st[i] = max(st[i * 2], st[i * 2 + 1]);
}
int query(int l, int r)
{
pair<int, int> p(-1, -1);
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) p = max(p, st[l++]);
if (r & 1) p = max(p, st[--r]);
}
return p.second;
}
};
sgt s;
void make(int l, int r, string& ans)
{
if (r < l) return;
int i = s.query(l, r);
if (l < i) ans.push_back('1');
else ans.push_back('0');
if (r > i) ans.push_back('1');
else ans.push_back('0');
make(l, i - 1, ans);
make(i + 1, r, ans);
}
void read_array(int subtask_id, const vector<int> &v)
{
s.init(v);
string ans;
if (v.size()<=500)
make(0, v.size() - 1, ans);
else {for(int i=0; i<v.size()-1; ++i) ans+="10"; ans+="00";}
save_to_floppy(ans);
}
int tim = 0; // :) :wave:
int val;
vector<int> v2;
int dfs(int u, const string &b)
{
int x = val, siz = 1; val--;
if (b[u * 2] == '1') siz += dfs(u + 1, b);
v2[tim++] = x;
if (b[u * 2 + 1] == '1') siz += dfs(u + siz, b);
return siz;
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
val = n - 1;
v2.resize(n, -1);
dfs(0, bits);
s.init(v2);
vector<int> ans;
for (int i = 0; i < a.size(); i++) ans.push_back(s.query(a[i], b[i]));
return ans;
}
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | else {for(int i=0; i<v.size()-1; ++i) ans+="10"; ans+="00";}
| ~^~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:91:31: 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++) ans.push_back(s.query(a[i], b[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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
824 KB |
Output is correct |
| 2 |
Correct |
1 ms |
820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
820 KB |
Output is correct |
| 4 |
Correct |
1 ms |
832 KB |
Output is correct |
| 5 |
Correct |
1 ms |
820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
4272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
15744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
