# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
800173 | 2023-08-01T11:16:47 Z | M7kra | Floppy (RMI20_floppy) | C++17 | 30 ms | 3904 KB |
#include <stdlib.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; #include "floppy.h" struct Bits { string bits = ""; void add(bool b) { if (b) bits += "1"; else bits += "0"; } string get() { return bits; } }; void read_array(int subtask_id, const std::vector<int> &v) { vector<int> numbers(v); Bits bits; sort(numbers.begin(), numbers.end(), [&bits](int a, int b) mutable { bits.add(a < b); return a < b; }); //cout << bits.get() << "\n"; save_to_floppy(bits.get()); } struct DBits { string bits; int index; DBits(string bits) { this->bits = bits; index = 0; } bool get() { return bits[index++] == '1'; } }; struct STree { int n; vector<int> elements; vector<int> best_index; STree (int size) { n = best2power(size); elements = vector<int>(n * 2); best_index = vector<int>(n * 2); } void update(int k, int x) { k += n; elements[k] = x; best_index[k] = k - n; for (k /= 2; k >= 1; k /= 2) { int a = k * 2; int b = a + 1; if (elements[a] > elements[b]) { elements[k] = elements[a]; best_index[k] = best_index[a]; } else { elements[k] = elements[b]; best_index[k] = best_index[b]; } } } int get(int a, int b) { a += n; b += n; int best = -1; int index = -1; while (a <= b) { if (a & 1) { if (elements[a] > best) { best = elements[a]; index = best_index[a]; } a++; } if ((b & 1) == 0) { if (elements[b] > best) { best = elements[b]; index = best_index[b]; } b--; } a /= 2; b /= 2; } return index; } int best2power(int n) { int i = 1; while (i < n) i *= 2; return i; } }; std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) { DBits dbits(bits); vector<int> numbers(N); for (int i = 0; i < N; i++) numbers[i] = i; sort(numbers.begin(), numbers.end(), [&dbits](int a, int b) { return dbits.get(); }); vector<int> result(N); for (int i = 0; i < N; i++) result[numbers[i]] = i; /*for (int i = 0; i < N; i++) { if (i) cout << " "; cout << result[i]; } cout << "\n";*/ STree stree(N); for (int i = 0; i < N; i++) { stree.update(i, result[i]); } vector<int> answers(a.size()); for (int i = 0; i < a.size(); i++) { answers[i] = stree.get(a[i], b[i]); } return answers; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 796 KB | Output is correct |
2 | Correct | 2 ms | 800 KB | Output is correct |
3 | Correct | 2 ms | 664 KB | Output is correct |
4 | Correct | 2 ms | 788 KB | Output is correct |
5 | Correct | 2 ms | 788 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Partially correct | 30 ms | 3904 KB | Partially correct |
2 | Partially correct | 27 ms | 3832 KB | Partially correct |
3 | Partially correct | 25 ms | 3652 KB | Partially correct |
4 | Incorrect | 7 ms | 1580 KB | L is too large |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 26 ms | 3412 KB | L is too large |
2 | Halted | 0 ms | 0 KB | - |