oj.uz

Submission #391350

# Submission time Handle Problem Language Result Execution time Memory
391350 2021-04-18T15:51:11 Z arwaeystoamneg Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 3652 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}

#ifndef arwaeystoamneg
#include "elephants.h"
#endif

const int MAX = 150005;
int n, a[MAX], l;
vi cur;
void init(int N, int L, int X[])
{
	n = N;
	l = L;
	F0R(i, n)a[i] = X[i];
	F0R(i, n)cur.pb(a[i]);
	sort(all(cur));
}
int query()
{
	int i = 0;
	int ans = 0, last = -inf;
	while (i < n)
	{
		if (cur[i] - last > l)
		{
			ans++;
			last = cur[i];
		}
		i++;
	}
	return ans;
}
int update(int i, int y)
{
	int p = find(all(cur), a[i]) - cur.begin();
	a[i] = y;
	cur[p] = y;
	while (p<n - 1 && cur[p] > cur[p + 1])swap(cur[p], cur[p + 1]), p++;
	while (p > 0 && cur[p - 1] > cur[p])swap(cur[p - 1], cur[p]), p--;
	return query();
}


#ifdef arwaeystoamneg
#define MAX_N 1000000
#define MAX_M 1000000

static int N, L, M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];

inline
void my_assert(int e) { if (!e) abort(); }

void read_input()
{
	int i;
	my_assert(3 == scanf("%d %d %d", &N, &L, &M));
	for (i = 0; i < N; i++)
		my_assert(1 == scanf("%d", &X[i]));
	for (i = 0; i < M; i++)
		my_assert(3 == scanf("%d %d %d", &ii[i], &yy[i], &sol[i]));
}

int main()
{
	setIO("test1");
	int i, ans;

	read_input();
	init(N, L, X);
	for (i = 0; i < M; i++) {
		ans = update(ii[i], yy[i]);
		if (ans == sol[i])continue;
		printf("Incorrect.  In %d-th move, answered %d (%d expected).\n",
			i + 1, ans, sol[i]);
		return 0;
	}
	printf("Correct.\n");
	return 0;
}


#endif

Compilation message

elephants.cpp: In function 'void setIO(std::string)':
elephants.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2013 ms 1108 KB Output is correct
8 Correct 2948 ms 1228 KB Output is correct
9 Correct 2831 ms 1604 KB Output is correct
10 Correct 5144 ms 2976 KB Output is correct
11 Correct 5432 ms 2916 KB Output is correct
12 Correct 8614 ms 3012 KB Output is correct
13 Correct 5480 ms 2776 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2013 ms 1108 KB Output is correct
8 Correct 2948 ms 1228 KB Output is correct
9 Correct 2831 ms 1604 KB Output is correct
10 Correct 5144 ms 2976 KB Output is correct
11 Correct 5432 ms 2916 KB Output is correct
12 Correct 8614 ms 3012 KB Output is correct
13 Correct 5480 ms 2776 KB Output is correct
14 Correct 2024 ms 2916 KB Output is correct
15 Correct 5752 ms 2916 KB Output is correct
16 Execution timed out 9020 ms 3652 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2013 ms 1108 KB Output is correct
8 Correct 2948 ms 1228 KB Output is correct
9 Correct 2831 ms 1604 KB Output is correct
10 Correct 5144 ms 2976 KB Output is correct
11 Correct 5432 ms 2916 KB Output is correct
12 Correct 8614 ms 3012 KB Output is correct
13 Correct 5480 ms 2776 KB Output is correct
14 Correct 2024 ms 2916 KB Output is correct
15 Correct 5752 ms 2916 KB Output is correct
16 Execution timed out 9020 ms 3652 KB Time limit exceeded
17 Halted 0 ms 0 KB -