제출 #954280

#제출 시각아이디문제언어결과실행 시간메모리
954280TAhmed33Floppy (RMI20_floppy)C++17
0 / 100
80 ms18352 KiB
#include <bits/stdc++.h> using namespace std; #include "floppy.h" const int MAXN = 4e4 + 25; int a[MAXN], n; int nxt[MAXN], prv[MAXN]; vector <int> adj[MAXN]; string ret; void dfs (int pos) { sort(adj[pos].begin(), adj[pos].end()); if (adj[pos].empty()) { ret += "00"; return; } if (adj[pos].size() == 1) { if (adj[pos][0] > pos) { ret += "01"; } else { ret += "10"; } dfs(adj[pos][0]); } else { ret += "11"; dfs(adj[pos][0]); dfs(adj[pos][1]); } } void read_array(int subtask_id, const std::vector<int> &v) { n = v.size(); for (int i = 1; i <= n; i++) a[i] = v[i - 1]; stack <int> cur; cur.push(1); for (int i = 2; i <= n; i++) { while (!cur.empty() && a[cur.top()] < a[i]) { nxt[cur.top()] = i; cur.pop(); } cur.push(i); } while (!cur.empty()) { nxt[cur.top()] = -1; cur.pop(); } cur.push(n); for (int i = n - 1; i >= 1; i--) { while (!cur.empty() && a[cur.top()] < a[i]) { prv[cur.top()] = i; cur.pop(); } cur.push(i); } while (!cur.empty()) { prv[cur.top()] = -1; cur.pop(); } int root = -1; for (int i = 1; i <= n; i++) { if (nxt[i] == -1 && prv[i] == -1) { root = i; continue; } if (nxt[i] == -1) { adj[prv[i]].push_back(i); continue; } if (prv[i] == -1) { adj[nxt[i]].push_back(i); continue; } if (a[nxt[i]] < a[prv[i]]) { adj[nxt[i]].push_back(i); } else { adj[prv[i]].push_back(i); } } dfs(root); assert((int)ret.size() == 2 * n); save_to_floppy(ret); } int deg[MAXN]; vector <int> inorder; int L[MAXN], R[MAXN]; int idx[MAXN]; int dp[20][MAXN], dep[MAXN]; void dfs2 (int pos) { if (L[pos] != -1) { dp[0][L[pos]] = pos; dep[L[pos]] = 1 + dep[pos]; dfs2(L[pos]); } inorder.push_back(pos); if (R[pos] != -1) { dp[0][R[pos]] = pos; dep[R[pos]] = 1 + dep[pos]; dfs2(R[pos]); } } int jump (int a, int b) { for (int i = 19; i >= 0; i--) { if (b & (1 << i)) { a = dp[i][a]; } } return a; } int lca (int a, int b) { if (dep[a] > dep[b]) swap(a, b); b = jump(b, dep[b] - dep[a]); if (a == b) return a; for (int i = 19; i >= 0; i--) { int x = dp[i][a], y = dp[i][b]; if (x && y && x != y) { a = x, b = y; } } return dp[0][a]; } 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; vector <int> ret; stack <int> cur; for (int i = 1; i <= n; i++) { deg[i] = (bits[2 * i - 2] == '1') + (bits[2 * i - 1] == '1'); } cur.push(1); for (int i = 2; i <= n; i++) { while (!cur.empty()) { if (deg[cur.top()] == 0) cur.pop(); else { adj[cur.top()].push_back(i); deg[cur.top()]--; break; } } cur.push(i); } for (int i = 1; i <= n; i++) { L[i] = R[i] = -1; sort(adj[i].begin(), adj[i].end()); bool f = 0; if (bits[2 * i - 2] == '1') { L[i] = adj[i][0]; f = 1; } if (bits[2 * i - 1] == '1') { R[i] = (f ? adj[i][1] : adj[i][0]); } } inorder.push_back(0); dfs2(1); for (int i = 1; i <= n; i++) { idx[i] = inorder[i]; } for (int i = 1; i < 20; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][dp[i - 1][j]]; } } for (int i = 0; i < (int)a.size(); i++) { ret.push_back(inorder[lca(idx[a[i] + 1], idx[b[i] + 1])] - 1); } return ret; }

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

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...