Submission #642651

#	Time	Username	Problem	Language	Result	Execution time	Memory
642651		TimDee	Floppy (RMI20_floppy)	C++17	28 / 100	64 ms	8424 KiB

floppy

#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;

void read_array(int subtask_id, const std::vector<int> &V) {
    vector<int> v=V;
    int n=v.size();
    if (subtask_id!=3) {
        vector<pair<int,int>> a(n);
        for (int i=0; i<n; ++i) {
            a[i]={v[i],i};
        }
        sort(a.begin(), a.end());
        for (int i=0; i<n; ++i) {
            v[a[i].second]=i;
        }

        int k=log2(n);
        string s;
        for (int i=0; i<n; ++i) {
            string t;
            for (int bit=k; bit>=0; --bit) {
                t+=('0'+((v[i]>>bit)&1));
            }
            s+=t;
        }

        save_to_floppy(s);
    } else {

        string S;
        vector<int> now;
        vector<int> tmp;
        v.push_back(-INT_MAX);
        for (int i=0; i<n; ++i) now.push_back(i);
        vector<int> ans;

        vector<vector<int>> won(n);
        
        while (now.size()>1) {
            if (now.size()&1) now.push_back(n);
            for (int i=0; i<now.size(); i+=2) {
                int f=now[i],s=now[i+1];
                if (v[f]>v[s]) {
                    if (s!=n) won[f].push_back(s);
                    S+='0';
                    tmp.push_back(f);
                } else {
                    won[s].push_back(f);
                    S+='1';
                    tmp.push_back(s);
                }
            }
            now=tmp;
            tmp.clear();
        }
        ans.push_back(now[0]);

        while (ans.size()<n) {
            now.clear();
            for (auto x:won[ans.back()]) {
                now.push_back(x);
            }
            while (now.size()>1) {
                if (now.size()&1) now.push_back(n);
                for (int i=0; i<now.size(); i+=2) {
                    int f=now[i],s=now[i+1];
                    if (v[f]>v[s]) {
                        if (s!=n) won[f].push_back(s);
                        S+='0';
                        tmp.push_back(f);
                    } else {
                        won[s].push_back(f);
                        S+='1';
                        tmp.push_back(s);
                    }
                }
                now=tmp;
                tmp.clear();
            }
            ans.push_back(now[0]);
        }

        save_to_floppy(S);

    }

}

vector<int> t;
vector<int> A;
int sz=1, neutr; 

int merge (int i, int j) {
    if (A[i]>A[j]) return i;
    else return j;
}

void update(int i, int l, int r) {
    if (r-l==1) return;
    int mid=(l+r)>>1;
    update(2*i+1,l,mid);
    update(2*i+2,mid,r);
    t[i]=merge(t[2*i+1],t[2*i+2]);
}

int query(int i, int l, int r, int lx, int rx) {
    if (l>=rx) return neutr;
    if (r<=lx) return neutr;
    if (l>=lx && r<=rx) return t[i];
    int mid=(l+r)>>1;
    int L=query(2*i+1,l,mid,lx,rx), R=query(2*i+2,mid,r,lx,rx);
    return merge(L,R);
}

int query(int l, int r) {
    return query(0,0,sz,l,r);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    int n=N,m=a.size();
    int k=log2(n); while (sz<n) sz<<=1;
    t.assign(2*sz-1,n);
    string S=bits;
    vector<int> v(n);
    if (subtask_id!=3) {
        for (int i=0; i<1ll*n*(k+1); i+=k+1) {
            int x=0;
            for (int bit=k; bit>=0; --bit) {
                x+=((S[i+k-bit]=='1')<<bit);
            }
            v[i/(k+1)]=x;
        }
    } else {

        int ptr=0;
        vector<int> now;
        vector<int> tmp;
        for (int i=0; i<n; ++i) now.push_back(i);
        vector<int> ans;

        vector<vector<int>> won(n);
        
        while (now.size()>1) {
            if (now.size()&1) now.push_back(n);
            for (int i=0; i<now.size(); i+=2) {
                int f=now[i],s=now[i+1];
                if (S[ptr++]=='0') {
                    if (s!=n) won[f].push_back(s);
                    tmp.push_back(f);
                } else {
                    won[s].push_back(f);
                    tmp.push_back(s);
                }
            }
            now=tmp;
            tmp.clear();
        }
        ans.push_back(now[0]);

        while (ans.size()<n) {
            now.clear();
            for (auto x:won[ans.back()]) {
                now.push_back(x);
            }
            while (now.size()>1) {
                if (now.size()&1) now.push_back(n);
                for (int i=0; i<now.size(); i+=2) {
                    int f=now[i],s=now[i+1];
                    if (S[ptr++]=='0') {
                        if (s!=n) won[f].push_back(s);
                        tmp.push_back(f);
                    } else {
                        won[s].push_back(f);
                        tmp.push_back(s);
                    }
                }
                now=tmp;
                tmp.clear();
            }
            ans.push_back(now[0]);
        }

        for (int i=0; i<n; ++i) {
            v[ans[i]]=n-1-i;
        }
    }
    neutr=n;
    v.push_back(-INT_MAX);
    A=v;
    for (int i=0; i<n; ++i) t[sz-1+i]=i;
    update(0,0,sz);
    vector<int> ans(m,0);
    for (int q=0; q<m; ++q) {
        int l=a[q], r=b[q];
        ans[q]=query(l,r+1);
    }
    return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for (int i=0; i<now.size(); i+=2) {
      |                           ~^~~~~~~~~~~
floppy.cpp:59:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         while (ans.size()<n) {
      |                ~~~~~~~~~~^~
floppy.cpp:66:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 for (int i=0; i<now.size(); i+=2) {
      |                               ~^~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:146:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for (int i=0; i<now.size(); i+=2) {
      |                           ~^~~~~~~~~~~
floppy.cpp:161:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |         while (ans.size()<n) {
      |                ~~~~~~~~~~^~
floppy.cpp:168:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |                 for (int i=0; i<now.size(); i+=2) {
      |                               ~^~~~~~~~~~~
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: 0 / 72