oj.uz

답안 #790711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790711 2023-07-23T06:43:21 Z PoonYaPat 커다란 상품 (IOI17_prize) C++14
0 / 100
 10 ms 9860 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int mmax=0,st,n,non_lol;
vector<int> val[200005];
vector<int> none;

int Ask(int x) {
    if (!val[x].size()) val[x]=ask(x);
}

void solve(int l, int r) { //l and r must be lolli_pop
    Ask(l);
    Ask(r);
    if (val[r][0]==val[l][0]) return;
    if (val[r][0]-val[l][0]==r-l-1) {
        for (int i=l+1; i<r; ++i) none.push_back(i);
    } else {
        int mid=(l+r)/2;
        Ask(mid);

        if (val[mid][0]+val[mid][1]!=mmax) {
            none.push_back(mid);
            
            for (int i=mid-1; i>l; --i) {
                Ask(i);
                if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
                else {
                    solve(l,i);
                    break;
                }
            }

            for (int i=mid+1; i<r; ++i) {
                Ask(i);
                if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
                else {
                    solve(i,r);
                    break;
                }
            }

        } else {
            solve(l,mid);
            solve(mid,r);
        }
    }

}

int find_best(int N) {
	n=N;
	for (int i=0; i<min(500,n); ++i) {
		val[i]=ask(i);
		mmax=max(mmax,val[i][0]+val[i][1]);
	}
    int st,ed;
    for (int i=0; i<n; ++i) {
        Ask(i);
        if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
        else {
            st=i;
            break;
        }
    }

    for (int i=n-1; i>=0; --i) {
        Ask(i);
        if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
        else {
            ed=i;
            break;
        }
    }

    solve(st,ed);

	for (auto s : none) {
		Ask(s);
		if (val[s][0]+val[s][1]==0) return s;
	}
}

Compilation message

prize.cpp: In function 'int Ask(int)':
prize.cpp:11:1: warning: no return statement in function returning non-void [-Wreturn-type]
   11 | }
      | ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^
prize.cpp:14:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 |     Ask(l);
      |     ~~~^~~
prize.cpp:58:9: note: 'st' was declared here
   58 |     int st,ed;
      |         ^~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 9840 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 9860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -