Submission #1056041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056041		ssense	Floppy (RMI20_floppy)	C++14	28 / 100	24 ms	6772 KiB

floppy

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include "floppy.h"
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
 
#define fr first
#define sc second
 
using namespace std;

// #define NMAX 100000
// #define MMAX 100000

// int subtask_id, N, M;
// std::vector<int> v, sorted_v;
// std::vector<int> a, b;
// std::vector<int> correct_answers;

// // Print score to stdout and exit.
// void score_and_exit(const double pts, const char *verdict) {
//     fprintf(stderr, "%s", verdict);
//     fprintf(stdout, "%f", pts);
//     exit(0);
// }

// // Contestant sent too many bits.
// void too_many_bits() {
//     score_and_exit(0, "Too many stored bits!");
// }

// // Contestant did not send any bits.
// void misformatted_stored_bits() {
//     score_and_exit(0, "Misformatted stored bits or save_to_floppy not called!");
// }

// // Contestant did not call the answer function.
// void answer_not_provided() {
//     score_and_exit(0, "Answer not provided!");
// }

// // Contestant sent a wrong answer.
// void wrong_answer() {
//     score_and_exit(0, "Wrong answer to query!");
// }

// // Contestant sent a correct answer.
// void correct_answer() {
//     score_and_exit(1, "OK!");
// }

// void read_test() {
//     assert(scanf("%d", &subtask_id) == 1);
//     assert(scanf("%d%d", &N, &M) == 2);
//     assert(1 <= N && N <= NMAX);
//     assert(0 <= M && M <= MMAX);
//     v.resize(N);
//     for (int i = 0; i < N; ++i) {
//         assert(scanf("%d", &v[i]) == 1);
//     }

//     // Check all values are distinct.
//     sorted_v.resize(N);
//     for (int i = 0; i < N; ++i) {
//         sorted_v[i] = v[i];
//     }
//     std::sort(sorted_v.begin(), sorted_v.end());
//     for (int i = 0; i + 1 < N; ++i) {
//         assert(sorted_v[i] < sorted_v[i + 1]);
//     }

//     a.resize(M);
//     b.resize(M);
//     correct_answers.resize(M);
//     for (int i = 0; i < M; ++i) {
//         assert(scanf("%d%d%d", &a[i], &b[i], &correct_answers[i]) == 3);
//         assert(0 <= a[i] && a[i] <= correct_answers[i] &&
//               correct_answers[i] <= b[i] && b[i] < N);
//     }
// }

vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
    int len = 0;
    if(subtask_id <= 2)
    {
        len = 14;
    }
    else
    {
        len = 16;
    }
    vector<int> arr(n);
    int st[len+1][n+1];
    for(int i = 0; i < bits.size(); i+=len)
    {
        int pos = 0;
        for(int j = i; j < i+len; j++)
        {
            if(bits[j] == '1')
            {
                pos+=1<<(j-i);
            }
        }
        // cout << "POS FIRST " << pos << endl;
        arr[pos] = n-i/len;
    }
    // cout << "BRUH BRUH" << endl;
    for(int i = 0; i < n; i++)
    {
        st[0][i] = i;
    }
    for(int i = 1; i <= len; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(j+(1<<(i-1)) >= n)
            {
                st[i][j] = st[i-1][j];
                continue;
            }
            if(arr[st[i-1][j]] > arr[st[i-1][j+(1<<(i-1))]])
            {
                st[i][j] = st[i-1][j];
            }
            else
            {
                st[i][j] = st[i-1][j+(1<<(i-1))];
            }
        }
    }
    // cout << "BRUH BRUH" << endl;
    vector<int> answers;
    for(int i = 0; i < a.size(); i++)
    {
        int l = a[i], r = b[i];
        int dist = 31-__builtin_clz(r-l+1);
        int ans;
        if(arr[st[dist][l]] > arr[st[dist][r-(1<<dist) + 1]])
        {
            ans = st[dist][l];
        }
        else
        {
            ans = st[dist][r-(1<<dist) + 1];
        }
        answers.push_back(ans);
    }
    // for(int i = 0; i < n; i++)
    // {
    //     cout << arr[i] << " ";
    // }
    // cout << endl;
    // for(int i = 0; i < answers.size(); i++)
    // {
    //     cout << "ANSWER: " << a[i] << " " << b[i] << " is " << answers[i] << endl;
    // }
    return answers;
}

// void save_to_floppy(const std::string &bits) {
//     std::vector<int> contestant_answers = solve_queries(subtask_id, N, bits, a, b);
//     for (int i = 0; i < M; ++i) {
//         if (contestant_answers[i] != correct_answers[i]) {
//             wrong_answer();
//         }
//     }
//     correct_answer();
//     exit(0);
// }

void read_array(int subtask_id, const vector<int> &v)
{
    int len = 0;
    if(subtask_id <= 2)
    {
        len = 14;
    }
    else
    {
        len = 16;
    }
    vector<pair<int, int> > a;
    for(int i = 0; i < v.size(); i++)
    {
        a.push_back(make_pair(v[i], i));
    }
    sort(a.begin(), a.end());
    string b = "";
    for(int i = v.size()-1; i >= 0; i--)
    {
        string nw = "";
        for(int j = 0; j < len; j++)
        {
            if((a[i].sc&(1<<j)) != 0)
            {
                nw.push_back('1');
            }
            else
            {
                nw.push_back('0');
            }
        }
        b+=nw;
    }
    save_to_floppy(b);
}

// int main(int argc, char **argv) {
//     // Read input data.
//     read_test();

//     // Send subtask_id, v.
//     read_array(subtask_id, v);
    
//     answer_not_provided();
//     return 0;
// }

 
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
*/
 
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < bits.size(); i+=len)
      |                    ~~^~~~~~~~~~~~~
floppy.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:199:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for(int i = 0; i < v.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: 0 / 72