#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
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
824 KB |
Output is correct |
| 2 |
Correct |
1 ms |
832 KB |
Output is correct |
| 3 |
Correct |
2 ms |
832 KB |
Output is correct |
| 4 |
Correct |
2 ms |
824 KB |
Output is correct |
| 5 |
Correct |
1 ms |
924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
4796 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4640 KB |
Output is correct |
| 3 |
Correct |
24 ms |
4704 KB |
Output is correct |
| 4 |
Correct |
19 ms |
4876 KB |
Output is correct |
| 5 |
Correct |
18 ms |
4784 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
23 ms |
6772 KB |
L is too large |
| 2 |
Halted |
0 ms |
0 KB |
- |
