제출 #1117099

#제출 시각아이디문제언어결과실행 시간메모리
1117099SonicMLFloppy (RMI20_floppy)C++14
0 / 100
24 ms5200 KiB
#include <stdlib.h> #include <string> #include <vector> #include "floppy.h" using namespace std; int n; int const NMAX = 40000; int arr[1 + NMAX]; string ans1; int ind = 0; void buildGraph(int from, int to) { if(from <= to) { int root = 0; for(int i = from;i <= to;i++) { if(arr[root] < arr[i]) { root = i; } } int node = ind; ans1[node * 2] = ans1[node * 2 + 1] = '0'; if(from < root) { ans1[node * 2] = '1'; ind++; buildGraph(from, root-1); } if(root < to) { ans1[node * 2 + 1] = '1'; ind++; buildGraph(root+1, to); } } } void read_array(int subtask_id, const std::vector<int> &v) { ind = 0; n = v.size(); for(int i = 1;i <= n;i++) { arr[i] = v[i-1]; } ans1.resize(2 * n); buildGraph(1, n); save_to_floppy(ans1); } int pos[1 + NMAX]; int nextNode = 0; void buildPos(int node) { if(ans1[node * 2] == '1') { nextNode++; buildPos(nextNode); } ind++; pos[node] = ind; if(ans1[node * 2 + 1] == '1') { nextNode++; buildPos(nextNode); } while(true) { //... } return; } bool compareArr(int a, int b) { return (arr[a] < arr[b]); } int const KMAX = 16; int rmq[1 + KMAX][1 + NMAX]; void buildRMQ() { for(int i = 0;i < n;i++) { arr[pos[i]] = i; } for(int i = 1;i <= n;i++) { rmq[0][i] = i; } for(int k = 1;k < KMAX;k++) { for(int i = 1;i <= n;i++) { int ii = min(n, i+(1<<(k-1))); if(compareArr(rmq[k-1][i], rmq[k-1][ii])) { rmq[k][i] = rmq[k-1][i]; }else { rmq[k][i] = rmq[k-1][ii]; } } } } int answerQuery(int from, int to) { int leng = (to - from + 1); int k = (31 - __builtin_clz(leng)); if(compareArr(rmq[k][from], rmq[k][to-(1<<k)+1])) { return rmq[k][from]; } else { return rmq[k][to-(1<<k)+1]; } } std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) { n = N; ind = 0; ans1 = bits; buildPos(0); buildRMQ(); vector <int> ans2; for(int i = 0;i < a.size();i++) { ans2.push_back(answerQuery(a[i]+1, b[i]+1)-1); } return ans2; }

컴파일 시 표준 에러 (stderr) 메시지

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i = 0;i < a.size();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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...