oj.uz

답안 #405966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405966 2021-05-17T05:50:58 Z jamezzz A Difficult(y) Choice (BOI21_books) C++14
5 / 100
 254 ms 14668 KB 
#include <bits/stdc++.h>
using namespace std;

#include "books.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef long long ll;
//less_equal for identical elements
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

long long a[100005];
bool use[100005];
pbds s;

void solve(int N, int K, long long A, int S) {
    if(N==S&&K==3){
		for(int i=1;i<=N;++i)a[i]=skim(i);
		for(int i=1;i<=N;++i){
			for(int j=i+1;j<=N;++j){
				for(int k=j+1;k<=N;++k){
					if(A<=a[i]+a[j]+a[k]&&a[i]+a[j]+a[k]<=2*A){
						answer({i,j,k});
						return;
					}
				}
			}
		}
		impossible();
	}
	else{
		memset(a,-1,sizeof a);
		ll sm=0;
		for(int i=1;i<=K;++i){
			a[i]=skim(i);
			sm+=a[i];
			use[i]=true;
		}
		if(2*A<sm)impossible();
		else{
			for(int i=K+1;i<=N;++i)s.insert(i);
			for(int i=1;i<=K;++i){
				int lo=1,hi=s.size(),mid,res;
				while(lo<=hi){
					mid=(lo+hi)/2;
					int val=*s.find_by_order(mid-1);
					if(a[val]==-1)a[val]=skim(val);
					if(A<=sm+a[val]-a[i]&&sm+a[val]-a[i]<=2*A){
						res=val;break;
					}
					else if(sm+a[val]-a[i]<A){
						lo=mid+1;
						res=val;
					}
					else hi=mid-1;
				}
				if(res!=0){
					s.erase(res);
					s.insert(i);
					sm+=a[res]-a[i];
				}
				if(A<=sm&&sm<=2*A){
					vector<int> ans;
					for(int i=1;i<=N;++i){
						if(s.find(i)==s.end())ans.push_back(i);
					}
					answer(ans);
					return;
				}
			}
			impossible();
		}
	}
}

Compilation message

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:74:15: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |      sm+=a[res]-a[i];
      |          ~~~~~^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 200 KB Output is correct
2 Correct 13 ms 200 KB Output is correct
3 Correct 16 ms 200 KB Output is correct
4 Correct 179 ms 200 KB Output is correct
5 Correct 11 ms 328 KB Output is correct
6 Correct 9 ms 200 KB Output is correct
7 Correct 14 ms 200 KB Output is correct
8 Correct 125 ms 300 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 200 KB Output is correct
2 Correct 12 ms 300 KB Output is correct
3 Correct 14 ms 200 KB Output is correct
4 Correct 179 ms 300 KB Output is correct
5 Correct 12 ms 296 KB Output is correct
6 Correct 17 ms 308 KB Output is correct
7 Correct 13 ms 304 KB Output is correct
8 Correct 141 ms 200 KB Output is correct
9 Correct 16 ms 2624 KB Output is correct
10 Correct 254 ms 552 KB Output is correct
11 Correct 16 ms 2616 KB Output is correct
12 Correct 16 ms 2620 KB Output is correct
13 Runtime error 15 ms 5056 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 7232 KB Output is correct
2 Correct 68 ms 7220 KB Output is correct
3 Correct 88 ms 7208 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 2 ms 968 KB Output is correct
6 Correct 1 ms 968 KB Output is correct
7 Correct 1 ms 968 KB Output is correct
8 Correct 80 ms 7220 KB Output is correct
9 Runtime error 76 ms 14668 KB Execution killed with signal 11

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 7232 KB Output is correct
2 Correct 68 ms 7220 KB Output is correct
3 Correct 88 ms 7208 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 2 ms 968 KB Output is correct
6 Correct 1 ms 968 KB Output is correct
7 Correct 1 ms 968 KB Output is correct
8 Correct 80 ms 7220 KB Output is correct
9 Runtime error 76 ms 14668 KB Execution killed with signal 11

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 7232 KB Output is correct
2 Correct 68 ms 7220 KB Output is correct
3 Correct 88 ms 7208 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 2 ms 968 KB Output is correct
6 Correct 1 ms 968 KB Output is correct
7 Correct 1 ms 968 KB Output is correct
8 Correct 80 ms 7220 KB Output is correct
9 Runtime error 76 ms 14668 KB Execution killed with signal 11

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 7232 KB Output is correct
2 Correct 68 ms 7220 KB Output is correct
3 Correct 88 ms 7208 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 2 ms 968 KB Output is correct
6 Correct 1 ms 968 KB Output is correct
7 Correct 1 ms 968 KB Output is correct
8 Correct 80 ms 7220 KB Output is correct
9 Runtime error 76 ms 14668 KB Execution killed with signal 11

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 7232 KB Output is correct
2 Correct 68 ms 7220 KB Output is correct
3 Correct 88 ms 7208 KB Output is correct
4 Correct 1 ms 968 KB Output is correct
5 Correct 2 ms 968 KB Output is correct
6 Correct 1 ms 968 KB Output is correct
7 Correct 1 ms 968 KB Output is correct
8 Correct 80 ms 7220 KB Output is correct
9 Runtime error 76 ms 14668 KB Execution killed with signal 11