| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 857994 | iulia_morariu | Floppy (RMI20_floppy) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <floppy.h>
using namespace std;
void read_array ( int subtask_id , vector<int> &v ){
vector < pair<int, int> > v1;
for(int i = 0; i < v.size(); i++){
v1.push_back( {v[i], i} );
}
sort(v1.begin(), v1.end());
int n = v.size();
/*
cout << "v1 : " << endl;
for(int i = 0; i < n; i++) cout << v1[i].first << " ";
cout << endl;
for(int i = 0; i < n; i++) cout << v1[i].second << " ";
cout << endl;*/
vector <string> b(v.size());
for(int i = 0; i < n; i++){
int i1 = i;
while( i1 > 0 ){
b[ v1[i].second ].push_back( char(i1 % 2 + '0') );
i1 /= 2;
}
while(b[ v1[i].second ].size() < 14) b[ v1[i].second ].push_back('0');
}
/*
cout << "b : " << endl;
for(int i = 0; i < n; i++){
cout << b[i] << endl;
}
*/
string s1;
for(int i = 0; i < n; i++){
for(int j = 0; j < b[i].size(); j++) s1.push_back( b[i][j] );
}
save_to_floppy(s1);
// cout << "s1 = " << s1 << endl;
}
vector<int> solve_queries ( int subtask_id , int N, string &bits, vector<int> &a, vector<int> &b ){
//cout << "bits : " << bits << endl;
int n = N;
int lg = log2(n) + 1;
int rmq[n][lg];
int p[n];
int pt = 1;
int it = 0;
for(int i = 0; i < n; i++) p[i] = 0;
for(int i = 0; i < bits.size(); i++){
//cout << "it = " << it << " i = " << i << " p[it] = " << p[it] << endl;
p[it] += pt * int(bits[i] - '0');
pt *= 2;
if( (i + 1) % 14 == 0 ){
pt = 1;
it++;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < lg; j++){
rmq[i][j] = 0;
}
}
for(int i = 0; i < n; i++){
rmq[i][0] = i;
}
pt = 1;
for(int j = 1; j < lg; j++){
for(int i = 0; i + pt < n; i++){
if( p[ rmq[i][j - 1] ] > p[ rmq[i + pt][j - 1] ] ){
rmq[i][j] = rmq[i][j - 1];
}else{
rmq[i][j] = rmq[i + pt][j - 1];
}
}
pt *= 2;
}
/*
cout << "rmq : " << endl;
for(int i = 0; i < n; i++){
for(int j = 0; j < lg; j++) cout << rmq[i][j] << " ";
cout << endl;
}*/
vector <int> sol;
for(int i = 0; i < a.size(); i++){
int l = min(a[i], b[i]), r = max(a[i], b[i]);
int pmax = l;
while(l <= r){
int l1 = log2(r - l + 1);
if( p[ rmq[l][l1] ] > p[pmax] ) pmax = rmq[l][l1];
l += pow(2, l1);
}
sol.push_back(pmax);
}
return sol;
}