Submission #1219950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219950		nikulid	Nile (IOI24_nile)	C++20	0 / 100	43 ms	15936 KiB

nile

#include "nile.h"
#include <algorithm>
#include <set>
#include <map>

// #include <iostream>


using namespace std;

/*

> ALL FOR SUBTASK 6	

*/

#define ll long long
#define pb push_back
#define mkp make_pair

#define dout if(1==1)cout

struct Node {
	int length;
	int nxt;
};

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
	
	int n = (int)W.size();
	int Q = (int)E.size();

	vector<ll> R(Q, 0);

	// W[] is the weights
  
	// start by sorting W in ascending order
	vector<pair<int, pair<int, int>>> ns(n);
	pair<int, pair<int, int>> p;
	int base_cost=0;
	for(int i=0; i<n; i++){
		p = mkp(W[i], mkp(A[i], B[i]));
		base_cost += A[i];
		ns[i] = p;
	}
	sort(ns.begin(), ns.end());
	
	vector<pair<ll, ll>> dp(n);
	vector<int> w(n),a(n),b(n);
	for(int i=0; i<n; i++){
		w[i] = ns[i].first;
		a[i] = ns[i].second.first;
		b[i] = ns[i].second.second;
	}
	
	// --- SUBTASK 6 ---
	// only w[] is relevant lol
	
	// init ds...
	vector<int> ds(n, 0);
	for(int i=1; i<n; i++){
		ds[i] = w[i] - w[i-1];
	}
	// ...
	

	// init sds...
	set<int> sds;
	for(int i=0; i<n; i++){
		sds.insert(ds[i]);
	}
	// ...
	

	// init arr
	vector<Node> arr;
	map<int, vector<int>> mp;
	
	int cur_length=1, cur_index=0, running_n_pairs = 0;
	for(int e=1; e<n; e++){
		if(ds[e] != 0){
			// aha! - an increase
			arr.pb(Node{cur_length, cur_index+1});
			running_n_pairs += cur_length/2;
			// sds already defined from line ~74
			mp[ds[e]].pb(cur_index);
			
			cur_length=1;
			cur_index++;
		} else{
			// no increase
			cur_length++;
		}
	}
	// final Node
	arr.pb(Node{cur_length, -1});
	running_n_pairs += cur_length/2;
	// no jump from here because it's the end
	
	// init increases...
	vector<pair<int, int>> increases;
	int val, cur_increases, size1, size2;
	vector<int> places;
	int i;
	for(auto it = sds.begin(); it != sds.end(); it++){
		val = *it;
		if(val==0)continue;
		// the next jump is D=`val`.
		
		//dout<<"[~113] next jump is D="<<val<<"...\n"; // DBUG
		
		cur_increases = 0;
		places = mp[val];

		for(int h=0; h<places.size(); h++){
			i = places[h];
			size1 = arr[i].length;
			size2 = arr[arr[i].nxt].length;
			arr[i].length= 		size1+size2;
			arr[arr[i].nxt].length=	size1+size2;
			//dout<<"i="<<i<<", LL indices "<<i<<" and "<<arr[i].nxt<<" have: ";
			//dout<<"merged strings of lengths "<<size1<<", "<<size2<<"\n";
			if(size1%2 == 1 && size2%2 == 1){
				//dout<<"INCR!";
				cur_increases++;
			}
		}

		if(cur_increases > 0){
			increases.pb(mkp((int)val, (int)cur_increases));
		}
		cur_increases = 0;
	}

	//dout<<"[131]\n";

	vector<int> ans(1e5+5);
	int current_runnings = running_n_pairs; // the base amount or wtv
	int next_jump = increases[0].first, next_increase = increases[0].second, idx=0;
	//dout<<"begin..\n";
	for(int i=0; i<1e5+5; i++){
		if(i == next_jump){
			current_runnings += next_increase;
			idx++;
			next_jump = increases[idx].first;
			next_increase = increases[idx].second;
		}
		ans[i] = current_runnings;
	}
	
	//dout<<"[146]\n";

	for(int i=0; i<Q; i++){
		R[i] = 2*(n - ans[E[i]]);
	}
	
	return R;
}


// -- DEBUG BELOW --
/*
int main(){
	cout<<"Hello World!\n";
	vector<int> w = {15, 12, 2, 10, 21};
	vector<int> a = {5, 4, 5, 6, 3};
	vector<int> b = {1, 2, 2, 3, 2};
	vector<int> e = {5, 9, 1};
	vector<ll> answers = calculate_costs(w, a, b, e);
	cout<<"\n\n";
	for(auto x:answers){
		cout<<x<<" ";
	}
	cout<<"\n\n";
	return 0;
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18