# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
596644 | 2022-07-14T23:21:42 Z | definitelynotmee | Floppy (RMI20_floppy) | C++17 | 99 ms | 11360 KB |
#include <stdlib.h> #include <string.h> #include "floppy.h" #include<bits/stdc++.h> #define ff first #define ss second #define all(x) x.begin(), x.end() using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using matrix = vector<vector<T>>; void read_array(int subtask_id, const std::vector<int> &v) { int n = v.size(); vector<int> jmp(n,-1); string bits; for(int i = 1; i < n; i++){ jmp[i] = i-1; while(jmp[i]!=-1 && v[jmp[i]] < v[i]) jmp[i] = jmp[jmp[i]], bits.push_back('0'); bits.push_back('1'); } 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) { vector<int> answers(b.size()); vector<int> jmp(n+1); int ptr = 0; for(int i = 2; i <= n; i++){ jmp[i] = i-1; while(true){ if(bits[ptr++] == '0'){ jmp[i] = jmp[jmp[i]]; } else break; } } matrix<int> lift(20,vector<int>(n+1)); for(int i = 0; i <= n; i++){ lift[0][i] = jmp[i]; } for(int i = 1; i < 20; i++){ for(int j = 0; j <= n; j++){ lift[i][j] = lift[i-1][lift[i-1][j]]; } } for(int i = 0; i < a.size(); i++){ int l = a[i]+1, r = b[i]+1; int id = r; for(int j = 19; j >= 0; j--){ if(lift[j][id] >= l) id = lift[j][id]; } answers[i] = id; } return answers; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 792 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 22 ms | 3264 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 99 ms | 11360 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |