oj.uz

답안 #789867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789867 2023-07-22T06:34:29 Z lollipop 커다란 상품 (IOI17_prize) C++17
20 / 100
 1000 ms 800 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "prize.h"

//static const int max_q = 10000;
//static int n;
//static int query_count = 0;
//static vector<int> g;
//static vector<vector<int> > rank_count;
//
//vector<int> ask(int i) {
//	query_count++;
//	if(query_count > max_q) {
//		cerr << "Query limit exceeded" << endl;
//		exit(0);
//	}
//
//	if(i < 0 || i >= n) {
//		cerr << "Bad index: " << i << endl;
//		exit(0);
//	}
//
//	vector<int> res(2);
//	res[0] = rank_count[g[i] - 1][i + 1];
//	res[1] = rank_count[g[i] - 1][n] - res[0];
//	return res;
//}


map < int , vector < int > > qu ; 
int been[ N ] ; 
int find_best(int n){
	int mx = 0 ;
	vector < int > pas ;  
	FOR( i , 1000 ){
	   pas = ask( i ) ;
	   if( pas[ 0 ] + pas[ 1 ] == 0 ) return i ;
	   mx = max( mx , pas[ 0 ] + pas[ 1 ] ) ; 	
	}
    vector < pair < int , int > > v ; 
    FOR( i , mx ) v.pb( { 0 , n - 1 } ) ; 
	while( true ){
		FOR( i , v.size() ){
			if( been[ i ] == 1 ) continue ;
	        int mid = ( v[ i ].f + v[ i ].s ) / 2 ;
	        if( qu.find( mid ) == qu.end() ) pas = ask( mid ) ;
			else pas = qu[ mid ] ; 
			qu[ mid ] = pas ; 
			if( pas[ 1 ] + pas[ 0 ] == 0 ) return mid ;
			if( v[ i ].f == v[ i ].s ) been[ i ] = 1 ;
			if( pas[ 1 ] < ( v.size() - i ) ) v[ i ].s = mid - 1 ;
			else v[ i ].f = mid + 1 ; 
		}
	}
}

//int main() {
//	cin >> n;
//
//	g.resize(n);
//	for(int i = 0; i < n; i++) {
//		cin >> g[i];
//		if(g[i] < 1) {
//			cerr << "Invalid rank " << g[i] << " at index " << i << endl;
//			exit(0);
//		}
//	}
//
//	int max_rank = *max_element(g.begin(), g.end());
//
//	rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
//	for(int r = 0; r <= max_rank; r++) {
//		for(int i = 1; i <= n; i++) {
//			rank_count[r][i] = rank_count[r][i - 1];
//			if(g[i - 1] == r)
//			  rank_count[r][i]++;
//		}
//	}
//
//	for(int i = 0; i <= n; i++)
//		for(int r = 1; r <= max_rank; r++)
//			rank_count[r][i] += rank_count[r - 1][i];
//
//	int res = find_best(n);
//	cout << res << endl << "Query count: " << query_count << endl;
//
//	return 0;
//}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   72 |   FOR( i , v.size() ){
      |        ~~~~~~~~~~~~                      
prize.cpp:72:3: note: in expansion of macro 'FOR'
   72 |   FOR( i , v.size() ){
      |   ^~~
prize.cpp:80:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    if( pas[ 1 ] < ( v.size() - i ) ) v[ i ].s = mid - 1 ;

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 304 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 8 ms 304 KB Output is correct
4 Correct 4 ms 308 KB Output is correct
5 Correct 4 ms 304 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 6 ms 284 KB Output is correct
8 Correct 11 ms 308 KB Output is correct
9 Correct 8 ms 304 KB Output is correct
10 Correct 10 ms 208 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 304 KB Output is correct
2 Correct 9 ms 308 KB Output is correct
3 Correct 7 ms 208 KB Output is correct
4 Correct 7 ms 304 KB Output is correct
5 Correct 8 ms 208 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 8 ms 208 KB Output is correct
8 Correct 5 ms 304 KB Output is correct
9 Correct 10 ms 208 KB Output is correct
10 Correct 10 ms 208 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 12 ms 308 KB Output is correct
13 Correct 6 ms 392 KB Output is correct
14 Correct 16 ms 352 KB Output is correct
15 Correct 32 ms 616 KB Output is correct
16 Correct 32 ms 612 KB Output is correct
17 Correct 3 ms 212 KB Output is correct
18 Correct 27 ms 584 KB Output is correct
19 Correct 3 ms 208 KB Output is correct
20 Correct 32 ms 460 KB Output is correct
21 Correct 15 ms 584 KB Output is correct
22 Correct 38 ms 592 KB Output is correct
23 Correct 7 ms 208 KB Output is correct
24 Correct 5 ms 324 KB Output is correct
25 Correct 22 ms 692 KB Output is correct
26 Partially correct 19 ms 732 KB Partially correct - number of queries: 5031
27 Correct 6 ms 304 KB Output is correct
28 Correct 20 ms 552 KB Output is correct
29 Correct 17 ms 644 KB Output is correct
30 Correct 36 ms 552 KB Output is correct
31 Correct 2 ms 308 KB Output is correct
32 Correct 7 ms 304 KB Output is correct
33 Correct 0 ms 208 KB Output is correct
34 Correct 29 ms 644 KB Output is correct
35 Correct 5 ms 304 KB Output is correct
36 Partially correct 21 ms 776 KB Partially correct - number of queries: 5328
37 Correct 5 ms 316 KB Output is correct
38 Correct 9 ms 308 KB Output is correct
39 Partially correct 44 ms 680 KB Partially correct - number of queries: 5392
40 Correct 25 ms 740 KB Output is correct
41 Partially correct 51 ms 684 KB Partially correct - number of queries: 5084
42 Partially correct 51 ms 740 KB Partially correct - number of queries: 5084
43 Correct 32 ms 592 KB Output is correct
44 Correct 32 ms 680 KB Output is correct
45 Correct 32 ms 656 KB Output is correct
46 Correct 2 ms 308 KB Output is correct
47 Partially correct 26 ms 776 KB Partially correct - number of queries: 5060
48 Partially correct 24 ms 708 KB Partially correct - number of queries: 5118
49 Correct 29 ms 556 KB Output is correct
50 Partially correct 47 ms 692 KB Partially correct - number of queries: 5278
51 Partially correct 45 ms 764 KB Partially correct - number of queries: 5398
52 Partially correct 44 ms 712 KB Partially correct - number of queries: 5291
53 Correct 10 ms 208 KB Output is correct
54 Correct 22 ms 572 KB Output is correct
55 Correct 2 ms 208 KB Output is correct
56 Partially correct 22 ms 800 KB Partially correct - number of queries: 5625
57 Correct 35 ms 556 KB Output is correct
58 Execution timed out 3016 ms 720 KB Time limit exceeded
59 Halted 0 ms 0 KB -