Submission #492537

#	Time	Username	Problem	Language	Result	Execution time	Memory
492537		cadmiumsky	Floppy (RMI20_floppy)	C++14	100 / 100	115 ms	17916 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <stack>
#include <iostream>

#include "floppy.h"

using namespace std;

void read_array(int subtask_id, const std::vector<int> &v) {
  string bits="";
  stack<int> st;
  for(int i=0; i<v.size(); i++) {
    while(!st.empty() && st.top()<v[i]) {
      st.pop();
      bits+="1";
    }
    if(v.size()!=i+1)
      bits+="0";
    st.push(v[i]);
  }
  save_to_floppy(bits);
}

int father[40000][16];
vector<int> tree[40000];
int pin[40000];
int pout[40000];
int inp;
static void dfs(int x) {
  pin[x]=inp++;
  for(auto y:tree[x])
    dfs(y);
  pout[x]=inp-1;
}

static bool isanc(int x, int y) {
  return pin[x]<=pin[y] && pout[x]>=pout[y];
}
static int lca(int x, int y) {
  if(isanc(x,y))
    return x;
  if(isanc(x,y))
    return y;
  for(int i=15; i>=0; i--) {
    if(!isanc(father[x][i],y))
      x=father[x][i];
  }
  return father[x][0];
}

std::vector<int> solve_queries(int subtask_id, int n,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
  //cout << bits << '\n';
  stack<int> st;
  vector<int> ans;
  int ptr=0;
  for(int i=0,last; i<n; i++) {
    last=-1;
    while(ptr<bits.size() && bits[ptr]=='1') {
      last=st.top();
      st.pop();
      ptr++;
    }
    if(last!=-1)
      father[last][0]=i;
    last=-1;
    if(st.size())
      last=st.top();
    father[i][0]=last;
    st.push(i);
    ptr++;
  }
  int root=0;
  for(int i=0; i<n; i++) {
    //cout << father[i][0] <<' ';
    if(father[i][0]==-1)
      root=i;
    else
      tree[father[i][0]].push_back(i);
  }
  //cout << '\n';
  dfs(root);
  father[root][0]=root;
  for(int step=1; step<16; step++) {
    for(int i=0; i<n; i++)
      father[i][step]=father[father[i][step-1]][step-1];
  }
  for(int i=0; i<a.size(); i++) {
    ans.push_back(lca(a[i],b[i]));
  }
  return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:13:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int i=0; i<v.size(); i++) {
      |                ~^~~~~~~~~
floppy.cpp:18:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     if(v.size()!=i+1)
      |        ~~~~~~~~^~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(ptr<bits.size() && bits[ptr]=='1') {
      |           ~~~^~~~~~~~~~~~
floppy.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72