Submission #1258209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258209		allin27x	Triple Peaks (IOI25_triples)	C++20	79.24 / 100	139 ms	23112 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int ans = 0;
int n;
const int SQRT = 450;

ifstream fin("oii");
ofstream fout("ott");

void count1(vector<signed> &h){
	for (int idx = 0; idx<n; idx++){
		int x = h[idx];
		int idh = idx - x;
		if (idh < 0) continue;
		int y = h[idh] - x;
		if (y <= 0 || y==x) continue;
		int idy = idx + y;
		if (idy >= n) continue;
		if (h[idy] == y) ans++;
	}
}

void count2(vector<signed> &h){
	for (int idx = 0; idx<n; idx++){
		int x = h[idx];
		int idy = idx + x;
		if (idy >= n) continue;
		int y = h[idy];
		int idh = idx - y;
		if (idh < 0) continue;
		if (h[idh] == x + y) ans++;
	}	
}

void count3(vector<signed> &h){
	for (int idx = 0; idx<n; idx++){
		int x = h[idx];
		int idh = idx + x;
		if (idh >= n) continue;
		int y = h[idh] - x;
		if (y <= 0 || y==x) continue;
		int idy = idh + y;
		if (idy >= n) continue;
		if (h[idy] == y) ans++;
	}
}

void count4(vector<signed> &h){
	vector<vector<int>> tl(3*n);
	for (int i=0; i<n; i++){
		int j = i + h[i]; if (j >= 3*n) continue;
		tl[j].push_back(h[i]);
	}
	
	for (int idt = 0; idt<3*n; idt++){
		if (tl[idt].size() > SQRT){
			for (int idx = 0; idx < idt; idx++){
				int x = h[idx];
				int y = idt - idx; y -= x; 
				if (y<=0 || (y&1)) continue;
				y/=2; int idy = idt - y;
				int idh = idt - x - y;
				if (h[idh] == x+y && h[idy] == y) ans++;
			}
		} else {
			for (int y: tl[idt]){
				for (int hv: tl[idt]){
					int x = hv - y; if (x<=0) continue;
					int idx = idt - hv - y;
					if (idx <0) continue;
					if (h[idx] == x) ans++;

				}
			}
		}
	}
}


long long count_triples(std::vector<signed> h) {
	n = h.size(); ans = 0;
	auto rh = h; reverse(rh.begin(), rh.end());
	count1(h); count1(rh);
	count2(h); count2(rh);
	count3(h); 
	count4(h); 
	return ans;
}

vector<signed> tr;
vector<vector<signed>> best;
int nr = 0; int last = 0;
int nans = 0;

const int nwsz = 320;
const int nwnr = 500;

void comb(){
	vector<vector<signed>> p;
	for (int i=0; i<nwnr; i++){
		vector<signed> tr(nwsz); for (int i=0; i<nwsz ;i++) fin>>tr[i];
		p.push_back(tr);
	}
	for (int i=0; i<nwnr; i++){
		for (int j=0; j<nwnr; j++){
			vector<signed> tr2 = p[i]; for (int ir=0; ir<nwsz; ir++) tr2.push_back(p[j][ir]);
			int nw = count_triples(tr2);
			if (nw > nans) best.clear(), nans = nw;
			if (nw == nans && best.size()< 500) best.push_back(tr2);

		}
	}
}

void cut(int sz){
	vector<vector<signed>> bs;
	for (auto v: best){
		auto r = v; while((int)r.size() > sz) r.pop_back();
		bs.push_back(r);
	}
	int best = 0; vector<signed> tbh;
	for (auto v: bs){
		int nw = count_triples(v);
		if (nw > best) best =nw, tbh = v;
	}
	sz = min(sz,(int) tbh.size());
	cout<<'{';
	for (int i=0; i<sz-1; i++) cout<<tbh[i]<<','; 
	cout<<tbh[sz-1]<<"}\n";

}
std::vector<signed> construct_range(signed n, signed K) {
	vector<signed> fl = {3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5,3,1,2,1,4,3,2,7,6,5,2,3,4,1,2,1,3,3,2,5}; 
	vector<signed> res; 
	while (res.size() < n){
		for (int i=0; i<640; i++) res.push_back(fl[i]);
	}
	while (res.size() > n) res.pop_back();
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 2.305 / 5
• Subtask 9: 0.9247 / 5
• Subtask 10: 0.3964 / 5
• Subtask 11: 0.4625 / 5
• Subtask 12: 0.1542 / 5