oj.uz

답안 #766796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766796 2023-06-26T07:32:52 Z danikoynov 커다란 상품 (IOI17_prize) C++14
20 / 100
 79 ms 2032 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map < int, vector < int > > mp;
map < int, int > used;
int cnt = 0;
vector < int > local_ask(int idx)
{
    if (used[idx])
        return mp[idx];
    cnt ++;
    //if (cnt == 1e4)
    //  while(true);
    used[idx] = 1;
    mp[idx] = ask(idx);
    return mp[idx];
}

const int maxn = 2e5 + 10;
vector < int > st;
int best;
void solve_range(int l, int r)
{
    ///cout << l << " " << r << endl;
    int m = (l + r) / 2;
    vector < int > lf = local_ask(l);
    vector < int > rf = local_ask(r);
    while(m > l)
    {
        vector < int > mf = local_ask(m);
        if (mf[0] + mf[1] != best)
        {
            st.push_back(m);
            m --;
        }
        else
        {
            break;
        }
    }
    if (m == l)
    {
        m = (l + r) / 2 + 1;
        while(m < r)
        {
            vector < int > mf = local_ask(m);
            if (mf[0] + mf[1] != best)
                st.push_back(m), m ++;
            else
                break;
        }
    }
    if (m == r)
        return;

    vector < int > mf = ask(m);
    if (lf[0] != mf[0])
        solve_range(l, m);
    if (rf[0] != mf[0])
        solve_range(m, r);
}
int find_best(int n)
{
    vector < int > idc;
    for (int i = 0; i < n; i ++)
        idc.push_back(i);
    int nec = min(n, (int)sqrt(n) + 2);
    int mx = -1;
    for (int i = 0; i < nec; i ++)
    {
        vector < int > cur = local_ask(i);
        if (cur[0] + cur[1] > best)
        {
            best = cur[0] + cur[1];
            mx = i;
        }
    }
    int pt = n - 1;
    while(true)
    {
        vector < int > cur = local_ask(pt);
        if (cur[0] + cur[1] == best)
            break;
        pt --;
    }


    for (int i = 0; i < mx; i ++)
        st.push_back(i);
    for (int i = pt + 1; i < n; i ++)
        st.push_back(i);
    solve_range(mx, pt);

    for (int i = 0; i < st.size(); i ++)
    {
        vector < int > cur = ask(st[i]);
        if (cur[0] + cur[1] == 0)
            return st[i];
    }
    return -1;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < st.size(); i ++)
      |                     ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1352 KB Output is correct
2 Correct 5 ms 1436 KB Output is correct
3 Correct 4 ms 1428 KB Output is correct
4 Correct 3 ms 1440 KB Output is correct
5 Correct 3 ms 1440 KB Output is correct
6 Correct 3 ms 1436 KB Output is correct
7 Correct 5 ms 1412 KB Output is correct
8 Correct 4 ms 1432 KB Output is correct
9 Correct 4 ms 1436 KB Output is correct
10 Correct 6 ms 1352 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1432 KB Output is correct
2 Correct 6 ms 1432 KB Output is correct
3 Correct 5 ms 1352 KB Output is correct
4 Correct 5 ms 1352 KB Output is correct
5 Correct 5 ms 1436 KB Output is correct
6 Correct 3 ms 1436 KB Output is correct
7 Correct 5 ms 1436 KB Output is correct
8 Correct 4 ms 1352 KB Output is correct
9 Correct 7 ms 1352 KB Output is correct
10 Correct 6 ms 1352 KB Output is correct
11 Correct 13 ms 1432 KB Output is correct
12 Correct 12 ms 1436 KB Output is correct
13 Correct 12 ms 1432 KB Output is correct
14 Correct 21 ms 544 KB Output is correct
15 Partially correct 61 ms 1892 KB Partially correct - number of queries: 9201
16 Incorrect 79 ms 2032 KB Incorrect
17 Halted 0 ms 0 KB -