#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include "tournament.h"
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef long double ld;
///#define int ll
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define pp pop_back
#define pf push_front
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
const ll MOD = 998244353;
int n, c, r;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n = N, c= C, r = R;
int *k = K, *s = S, *e = E;
int curmax =0, curpos = 0;
for(int pos =0; pos < n; pos ++)
{
//cout << pos << endl;
indexed_set rem;
vi pow(n);
for(int i= 0; i < n; i++)
{
rem.insert(i);
pow[i] = (i < pos)? k[i]: i == pos? r: k[i - 1];
}
int now = 0;
for(int round = 0; round < c; round ++)
{
//cout << round << endl;
int maxi = 0;
for(int j = s[round]; j <= e[round]; j ++)
{
int u= *(rem.find_by_order(j));
// cout << j << ' ' << u << endl;
maxi = max(maxi, pow[u]);
}
//cout << "here" << endl;
now += (maxi == r);
vi remv;
bool flag= true;
for(int j = s[round]; j <= e[round]; j ++)
{
int u= *(rem.find_by_order(j));
if(pow[u] < maxi)
{
if(u == pos)
{
flag = false;
break;
}
remv.pb(u);
}
}
for(auto e: remv)
rem.erase(e);
if(!flag)
{
if(now > curmax)
{
curmax = now;
curpos = pos;
}
break;
}
}
}
//cout << curmax << '\n';
return curpos;
}
/*
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1; //'cin >> tt;
int N, C, R;
cin >> N >> C >> R;
int *K, *S, *E;
K = (int*) malloc((N-1) * sizeof(int));
S = (int*) malloc(C * sizeof(int));
E = (int*) malloc(C * sizeof(int));
for (int i = 0; i < N-1; i++)
{
scanf("%d", &K[i]);
}
for (int i = 0; i < C; i++)
{
scanf("%d %d", &S[i], &E[i]);
}
cout << GetBestPosition(N,C,R,K,S,E) ;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
296 KB |
Output is correct |
| 3 |
Correct |
63 ms |
316 KB |
Output is correct |
| 4 |
Correct |
58 ms |
212 KB |
Output is correct |
| 5 |
Correct |
52 ms |
300 KB |
Output is correct |
| 6 |
Correct |
67 ms |
340 KB |
Output is correct |
| 7 |
Correct |
74 ms |
312 KB |
Output is correct |
| 8 |
Correct |
73 ms |
212 KB |
Output is correct |
| 9 |
Correct |
54 ms |
212 KB |
Output is correct |
| 10 |
Correct |
57 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
1075 ms |
692 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1052 ms |
3276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
