oj.uz

Submission #919947

# Submission time Handle Problem Language Result Execution time Memory
919947 2024-02-01T23:13:17 Z Lalic Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 8804 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 15e4+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int arr[MAXN], proc[MAXN];
int l, n;

void init(int N, int L, int X[])
{
	for(int i=0;i<N;i++) arr[i]=X[i], proc[i]=X[i];
	l=L; n=N;
}

int update(int i, int y)
{
	int id;
	for(int j=0;j<n;j++){
		if(proc[j]==arr[i]){
			id=j;
			break;
		}
	}
	
	int val=proc[id];
	
	if(val>y){
		bool foi=0;
		for(int j=id-1;j>=0;j--){
			proc[j+1]=proc[j];
			if(proc[j]<y){
				proc[j+1]=y;
				foi=1;
				break;
			}
		}
		if(!foi) proc[0]=y;
	}
	else{
		bool foi=0;
		for(int j=id+1;j<n;j++){
			proc[j-1]=proc[j];
			if(proc[j]>y){
				proc[j-1]=y;
				foi=1;
				break;
			}
		}
		if(!foi) proc[n-1]=y;
	}
	
	arr[i]=y;
	
	int ans=0, curr=-l-1;
	for(int j=0;j<n;j++){
		if(proc[j]<=curr+l) continue;
		ans++;
		curr=proc[j];
	}
	
	return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:42:6: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |  int val=proc[id];
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1303 ms 8676 KB Output is correct
8 Correct 2431 ms 8692 KB Output is correct
9 Correct 2498 ms 8792 KB Output is correct
10 Correct 3115 ms 8792 KB Output is correct
11 Correct 3120 ms 8800 KB Output is correct
12 Correct 6957 ms 8804 KB Output is correct
13 Correct 3064 ms 8792 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1303 ms 8676 KB Output is correct
8 Correct 2431 ms 8692 KB Output is correct
9 Correct 2498 ms 8792 KB Output is correct
10 Correct 3115 ms 8792 KB Output is correct
11 Correct 3120 ms 8800 KB Output is correct
12 Correct 6957 ms 8804 KB Output is correct
13 Correct 3064 ms 8792 KB Output is correct
14 Correct 1651 ms 8692 KB Output is correct
15 Correct 5113 ms 8716 KB Output is correct
16 Execution timed out 9076 ms 8792 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1303 ms 8676 KB Output is correct
8 Correct 2431 ms 8692 KB Output is correct
9 Correct 2498 ms 8792 KB Output is correct
10 Correct 3115 ms 8792 KB Output is correct
11 Correct 3120 ms 8800 KB Output is correct
12 Correct 6957 ms 8804 KB Output is correct
13 Correct 3064 ms 8792 KB Output is correct
14 Correct 1651 ms 8692 KB Output is correct
15 Correct 5113 ms 8716 KB Output is correct
16 Execution timed out 9076 ms 8792 KB Time limit exceeded
17 Halted 0 ms 0 KB -