Submission #282500

#TimeUsernameProblemLanguageResultExecution timeMemory
282500youssefbou62Jousting tournament (IOI12_tournament)C++14
0 / 100
71 ms1408 KiB
#include <bits/stdc++.h> using namespace std; // using namespace __gnu_pbds; #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define mp make_pair #define fi first #define se second #define all(v) v.begin(),v.end() #define allarr(a) a , a + n #define ll long long #define ull unsigned long long #define pb push_back #define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL) #define sz(x) (int)x.size() typedef pair<int, int> pi; typedef pair<ll,ll> pll; typedef pair<int,pi> trp ; typedef vector<pi> vpi; typedef vector<pll> vpll ; // int ab (int x ) { return (x>0?x:-x); } //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int MAXN = 5005 ; int in[MAXN] ; int st[MAXN*2]; int v[MAXN]; void init(int n){ for(int i = 0 ; i< n ;i++ ) in[i] = i ; } int left(int u){return u*2+1;} int right(int u){return u*2+2;} void build (int i,int j,int in,int u){ if( i > j )return ; if( i == j ){ st[u] = v[in]; return ; } int mid = (i+j)/2; if( in <= mid ) build(i,mid,in,left(u)); else build(mid+1,j,in,right(u)); st[u] = max(st[left(u)],st[right(u)]); } int query(int i,int j,int qL ,int qR,int u){ if( i > j || i > qR || j < qL ) return -1; if( i >= qL && j <= qR )return st[u] ; int mid = ( i + j )/2; return max(query(i,mid,qL,qR,left(u)) , query(mid+1,j,qL,qR,right(u))); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { init(N); vpi queries ; for(int i = 0 ; i < C ; i++ ){ int s = S[i] , e = E[i] ; int new_index = s ; int L = 1e9 , R = -1 ; int last = -1 ; for(int j = 0 ; j < N ; j++ ){ if( in[j] >= s && in[j] <= e){ last = in[j] ; in[j] = new_index; L = min(L,j); R = max(R,j); } if( in[j] > e && in[j]!=last)new_index ++ ; if( in[j] > e ) last=in[j],in[j] = new_index ; } // for(int j = 0 ; j < N ; j++ )cout << in[j] << " " ; cout << endl; queries.pb({L,R}); } vector<int> bat , bat1 ; int ans=-1,pos; for(int i = 0 ; i < N-1 ; i++ )v[i] = K[i] ; for(int i = N-1 ; i != -1 ; i-- ){ v[i+1]=v[i]; v[i] = R; if( i < N-1 ) build(0,N-1,i+1,0); build(0,N-1,i,0); int cur_ans = 0 ; for(int j = 0 ; j < C ; j++ ){ if(query(0,N-1,queries[j].fi,queries[j].se,0)==R) cur_ans ++ ; } if( cur_ans >= ans ){ pos = i ; ans = cur_ans ; } } assert(ans!=-1); return pos; } // #define inbuf_len 1 << 16 // #define outbuf_len 1 << 16 // int GetBestPosition(int N, int C, int R, int *K, int *S, int *E); // int main() { // int tmp; // /* Set input and output buffering */ // char *inbuf, *outbuf; // inbuf = (char*) malloc(inbuf_len * sizeof(char)); // outbuf = (char*) malloc(outbuf_len * sizeof(char)); // tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len); // assert(tmp == 0); // tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len); // assert(tmp == 0); // int N, C, R; // int *K, *S, *E; // tmp = scanf("%d %d %d", &N, &C, &R); // assert(tmp == 3); // K = (int*) malloc((N-1) * sizeof(int)); // S = (int*) malloc(C * sizeof(int)); // E = (int*) malloc(C * sizeof(int)); // int i; // for (i = 0; i < N-1; i++) { // tmp = scanf("%d", &K[i]); // assert(tmp == 1); // } // for (i = 0; i < C; i++) { // tmp = scanf("%d %d", &S[i], &E[i]); // assert(tmp == 2); // } // printf("%d\n", GetBestPosition(N, C, R, K, S, E)); // return 0; // }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:118:11: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |    return pos;
      |           ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...