Submission #1369176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369176		dragonlyz123	Gift Boxes (EGOI25_giftboxes)	C++20	19 / 100	1669 ms	113908 KiB

Main

/*
─────────────────────────────────────────────────────────────────────────────────────
 ██╗     ███████╗███████╗    ██╗   ██╗███████╗███╗   ██╗    ███████╗███████╗███████╗
 ██║     ██╔════╝██╔════╝    ╚██╗ ██╔╝██╔══██╗████╗  ██║    ╚══███╔╝██╔════╝██╔════╝
 ██║     █████╗  █████╗       ╚████╔╝ ███████║██╔██╗ ██║      ███╔╝ █████╗  █████╗
 ██║     ██╔══╝  ██╔══╝        ╚██╔╝  ██╔══██║██║╚██╗██║     ███╔╝  ██╔══╝  ██╔══╝
 ███████╗███████╗███████╗       ██║   ██║  ██║██║ ╚████║    ███████╗███████╗███████╗
 ╚══════╝╚══════╝╚══════╝       ╚═╝   ╚═╝  ╚═╝╚═╝  ╚═══╝    ╚══════╝╚══════╝╚══════╝
 ─────────────────────────────────────────────────────────────────────────────────────
							» Stay hungry, stay foolish. «
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
ll ll_max = 2e18;
ll ll_min = -2e18;
 
void set_io(string name = "") {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

void solve() {
	ll t, n; cin >> t >> n;
	map<ll, ll> b;
	vector<ll> a(n);
	set<ll> d;
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
		b[a[i]]++;
		if (b[a[i]] > 1) d.emplace(a[i]);
	}
	map<ll, ll> c = b;
	set<ll> e = d;
	set<ll> z, y;
	ll l = -1, r = -1;
	for (ll i = 0; i < n; i++) {
		if (z.find(a[i]) == z.end()) {
			c[a[i]]--;
			if (c[a[i]] == 1) e.erase(a[i]);
			z.emplace(a[i]);
		} else {
			l = i;
			r = i;
			while (!e.empty() || z.find(a[r]) != z.end() ) {
				c[a[r]]--;
				if (c[a[r]] == 1) e.erase(a[r]);
				r++;
				if (r == n) break;
			}
			for (ll j = n - 1; j > r; j--) {
				if (z.find(a[j]) != z.end()) {
					r = j;
					break;
				} else {
					z.emplace(a[j]);
				}
			}
			break;
		}
	}
	ll l1 = -1, r1 = -1;
	for (ll i = n - 1; i >= 0; i--) {
		if (y.find(a[i]) == y.end()) {
			b[a[i]]--;
			if (b[a[i]] == 1) d.erase(a[i]);
			y.emplace(a[i]);
		} else {
			l1 = i;
			r1 = i;
			while (!d.empty() || y.find(a[l1]) != y.end()) {
				b[a[l1]]--;
				if (b[a[l1]] == 1) d.erase(a[l1]);
				l1--;
				if (l1 == -1) break;
			}
			for (ll j = 0; j < l1; j++) {
				if (y.find(a[j]) != y.end()) {
					l1 = j;
					break;
				} else {
					y.emplace(a[j]);
				}
			}
			break;
		}
	}
	if (r - l < r1 - l1) cout << l << " " << r - 1 << "\n";
	else cout << l1 + 1 << " " << r1 << "\n";
}

int main() {
    set_io();
    // ll t; cin >> t;
    // while (t--) {
    //     solve();
    // }
    solve();
    return 0;
}

// g++-15 -std=c++23 -O2 solution.cpp -o solution
// ./solution

Compilation message (stderr)

Main.cpp: In function 'void set_io(std::string)':
Main.cpp:26:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 freopen((name + ".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |                 freopen((name + ".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 22
• Subtask 6: 0 / 24