oj.uz

Submission #1067624

# Submission time Handle Problem Language Result Execution time Memory
1067624 2024-08-20T21:55:15 Z NemanjaSo2005 Floppy (RMI20_floppy) C++17
100 / 100
 839 ms 15976 KB 
#include<bits/stdc++.h>
#include "floppy.h"
#define ll long long
using namespace std;
const int maxn=40005;
int N,niz[maxn],K;
int st[4*maxn];
int get(int lg,int dg,int gde=1,int lc=1,int dc=K){
   if(lg==lc and dg==dc)
      return st[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return get(lg,dg,gde*2,lc,sred);
   if(lg>sred)
      return get(lg,dg,gde*2+1,sred+1,dc);
   int v1,v2;
   v1=get(lg,sred,gde*2,lc,sred);
   v2=get(sred+1,dg,gde*2+1,sred+1,dc);
   if(niz[v1]>niz[v2])
      return v1;
   return v2;
};
void makesegment(){
   K=1;
   while(K<N)
      K<<=1;
   for(int i=1;i<=N;i++)
      st[i+K-1]=i;
   niz[0]=-2e9;
   for(int i=K-1;i>=1;i--){
      if(niz[st[i*2]]>niz[st[i*2+1]])
         st[i]=st[i*2];
      else
         st[i]=st[i*2+1];
   }
}
void makestring(int l,int r,string &S){
   if(r<l)
      return;
   if(l==r){
      S.push_back('(');
      S.push_back(')');
      return;
   }
   int maks=get(l,r);
   makestring(l,maks-1,S);
   S.push_back('(');
   makestring(maks+1,r,S);
   S.push_back(')');
}
void read_array(int subtask_id, const std::vector<int> &v) {
   N=v.size();
   for(int i=1;i<=N;i++)
      niz[i]=v[i-1];
   string S;
   makesegment();
   makestring(1,N,S);

   cerr<<"STRING JE "<<S<<endl;

   for(int i=0;i<S.size();i++)
      if(S[i]=='(')
         S[i]='1';
      else
         S[i]='0';
   save_to_floppy(S);
}

void decode(string &S,int l,int r,int br=0,int pre=0){
   if(r<=l)
      return;
   //cerr<<l<<" "<<r<<endl;
   int poz,val=0;
   for(int i=r;i>=l;i--){
      val+=S[i];
      if(val==0){
         poz=i;
         break;
      }
   }
   int idx=(poz-l)/2+1+pre;
   cerr<<l<<" "<<r<<" "<<poz<<" "<<idx<<endl;
   niz[idx]=br;
   decode(S,l,poz-1,br-1,pre);
   decode(S,poz+1,r-1,br-1,idx);
}
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;
   string S=bits;
   for(int i=0;i<S.size();i++)
      if(S[i]=='1')
         S[i]=1;
      else
         S[i]=-1;
   decode(S,0,S.size()-1);
   cerr<<"REKONSTRUISAN NIZ"<<endl;
   for(int i=1;i<=N;i++)
      cerr<<niz[i]<<" ";
   cerr<<endl;
   makesegment();
   vector<int> V;
   for(int i=0;i<a.size();i++){
      int x=a[i]+1;
      int y=b[i]+1;
      V.push_back(get(x,y)-1);
   }
   return V;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int i=0;i<S.size();i++)
      |                ~^~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int i=0;i<S.size();i++)
      |                ~^~~~~~~~~
floppy.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    for(int i=0;i<a.size();i++){
      |                ~^~~~~~~~~
floppy.cpp: In function 'void decode(std::string&, int, int, int, int)':
floppy.cpp:81:16: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |    int idx=(poz-l)/2+1+pre;
      |            ~~~~^~~
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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 824 KB Output is correct
2 Correct 6 ms 824 KB Output is correct
3 Correct 6 ms 836 KB Output is correct
4 Correct 6 ms 828 KB Output is correct
5 Correct 6 ms 828 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 3932 KB Output is correct
2 Correct 111 ms 3672 KB Output is correct
3 Correct 140 ms 4316 KB Output is correct
4 Correct 118 ms 4156 KB Output is correct
5 Correct 114 ms 3664 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 14056 KB Output is correct
2 Correct 497 ms 14036 KB Output is correct
3 Correct 839 ms 15976 KB Output is correct
4 Correct 586 ms 15652 KB Output is correct
5 Correct 459 ms 14008 KB Output is correct