oj.uz

Submission #994874

# Submission time Handle Problem Language Result Execution time Memory
994874 2024-06-08T07:58:31 Z Bula Library (JOI18_library) C++17
0 / 100
 73 ms 416 KB 
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> p; 
int x = 0;
int ask(int l, int r, int idx){
    l--, r--; idx--; for(int i = 0; i < p.size(); i++) p[i] = 0;
    for(int i = l; i <= r; i++) p[i] = 1;
    if(idx != -1) p[idx] = 1;
    if(x) p[x - 1] = 0;
    return Query(p);
}
void Solve(int n){
    p.resize(n);
    vector<int> pref(n + 1), suf(n + 1);
    for(int i = 1; i <= n; i++){
        pref[i] = ask(1, i, 0);
        suf[i] = ask(i, n, 0);
    }
    vector<pair<int, int>> pr(n + 1);
    for(int i = 1; i <= n; i++){
        int l = 1, r = i - 1;
        while(l < r){
            int m = (l + r) / 2;
            if(ask(1, m, i) == pref[m]) r = m;
            else l = m + 1;
        }
        if(l == r && ask(1, l, i) == pref[l]) pr[i].first = l;
        if(!pr[i].first){
            l = i + 1, r = n;
            while(l < r){
                int m = (l + r + 1) / 2;
                if(ask(m, n, i) == suf[m]) l = m;
                else r = m - 1;
            }
            if(l == r && ask(l, n, i) == suf[l]) pr[i].first = l;
        }
        x = pr[i].first;
        l = 1, r = i - 1;
        while(l < r){
            int m = (l + r) / 2;
            if(ask(1, m, i) == ask(1, m, 0)) r = m;
            else l = m + 1;
        }
        if(l == r && ask(1, l, i) == (1, l, 0)) pr[i].second = l;
        if(!pr[i].second){
            l = i + 1, r = n;
            while(l < r){
                int m = (l + r + 1) / 2;
                if(ask(m, n, i) == ask(m, n, 0)) l = m;
                else r = m - 1;
            }
            if(l == r && ask(l, n, i) == ask(l, n, 0)) pr[i].second = l;
        }
        x = 0;
    }
    int k = 1; vector<int> ans;
    for(int i = 1; i <= n; i++){
        if(!pr[i].second) k = i;
    }
    vector<int> vis(n + 1); vis[0] = 1;
    while(ans.size() < n){
        ans.push_back(k); vis[k] = 1;
        if(!vis[pr[k].first]){
            k = pr[k].first;
        }else if(!vis[pr[k].second]){
            k = pr[k].second;
        }
    }
    Answer(ans);
}

Compilation message

library.cpp: In function 'int ask(int, int, int)':
library.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     l--, r--; idx--; for(int i = 0; i < p.size(); i++) p[i] = 0;
      |                                     ~~^~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:45:39: warning: left operand of comma operator has no effect [-Wunused-value]
   45 |         if(l == r && ask(1, l, i) == (1, l, 0)) pr[i].second = l;
      |                                       ^
library.cpp:45:45: warning: right operand of comma operator has no effect [-Wunused-value]
   45 |         if(l == r && ask(1, l, i) == (1, l, 0)) pr[i].second = l;
      |                                             ^
library.cpp:62:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     while(ans.size() < n){
      |           ~~~~~~~~~~~^~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 416 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 416 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -