oj.uz

Submission #763389

# Submission time Handle Problem Language Result Execution time Memory
763389 2023-06-22T09:02:33 Z burythelightdeepwithin Xylophone (JOI18_xylophone) C++14
0 / 100
 3 ms 208 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

const int N = 5003;
int ans[N];
vector <int> w;

void solve(int n){
    w.push_back(n+1);
    int l = 1, r = n;
    while(l < r){
        int mid = (l+r)/2;
        int x = query(1, mid);
        if (x == (n-1)){
            r = mid;
        } else {
            l = mid+1;
        }
    }
    ans[l] = n;
    w.push_back(l);
    l = 1, r = n;
    while(l < r){
        int mid = (l+r)/2 + ((l+r) % 2);
        int x = query(mid, n);
        if (x == (n-1)){
            l = mid;
        } else {
            r = mid-1;
        }
    }
    ans[l] = 1;
    w.push_back(l);
    for (int k = n-1; k > 1; k--){
        sort(w.begin(), w.end());
        int reset = 0;
        int l = 1, r = w[0]-1;
        while(l < r){
            int mid = (l+r)/2 + ((l+r) % 2);
            int x = query(mid, w[0] - 1);
            if (x == abs(ans[w[0]] - k)){
                l = mid;
            } else {
                r = mid-1;
            }
        }
        if (l == r){
            int x = query(l, w[0]);
            if (x == abs(ans[w[0]] - k)){
                reset = 1;
            }
        }
        for (int i = 1; i < (int)w.size() - 1; i++){
            if (reset){
                 break;
            }
            l = w[i] + 1, r = w[i+1] - 1;
            while(l < r){
                int mid = (l+r)/2;
                int x = query(w[i], mid);
                if (x == abs(ans[w[i]] - k)){
                    r = mid;
                    reset = 1;
                } else {
                    l = mid+1;
                }
            }
            if (l == r){
                int x = query(w[i], l);
                if (x == abs(ans[w[i]] - k)){
                    reset = 1;
                }
            }
        }
        ans[l] = k;
        w.push_back(l);
    }
    for (int i = 1; i <= n; i++){
        answer(i, ans[i]);
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 3 ms 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 3 ms 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 3 ms 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -