Submission #1021171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021171		mat_jur	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9064 ms	2780 KiB

elephants

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int n, l;
vector<int> x;
vector<int> idx;

void init(int _n, int _l, int _x[]) {
	n = _n; l = _l; 
	for (int i = 0; i < n; ++i) x.eb(_x[i]);
	idx.resize(n);
	iota(all(idx), 0);
}

int update(int _i, int y) {
	int i;
	for (i = 0; idx[i] != _i; ++i) ;

	debug(l);
	x[i] = y;
	while (i+1 < n && x[i] > x[i+1]) {
		swap(x[i], x[i+1]);
		swap(idx[i], idx[i+1]);
		++i;
	}
	while (i-1 >= 0 && x[i] < x[i-1]) {
		swap(x[i], x[i-1]);
		swap(idx[i], idx[i-1]);
		--i;
	}
	debug(x);

	int res = 0;
	for (int j = 0; j < n; ++j) {
		++res;
		int k = j;
		debug(x[j] + l);
		while (k+1 < n && x[j] + l >= x[k+1]) ++k;
		debug(j);
		debug(k);
		j = k;
	}

	return res;
}

#ifdef LOCAL
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, l, m;
	cin >> n >> l >> m;
	int *x = new int[n];
	for (int i = 0; i < n; ++i) cin >> x[i];
	init(n, l, x);

	for (int i = 0; i < m; ++i) {
		int j, y, s;
		cin >> j >> y >> s;
		int ans = update(j, y);
		cout << "ANS = " << ans << ", expected " << s << '\n';
		if (ans != s) cout << "WA on query " << i+1 << endl;
	}

	return 0;
}
#endif

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3