Problem Info
USACO 2016 US Open Contest, Silver; Problem 2. Diamond Collector + link to problem here
Question
I have no idea what’s wrong with my code, all testcases pass except 5, 6 & 10.
What I’ve Tried
I’ve tried testing with various testcases, long long, out of bound access verification, etc. Nothing worked.
My Work
//
// Created by VJ09743
//
#include <bits/stdc++.h>
#define scint "%d"
#define scll "%lld"
#define int long long
//#define scint scll
#define scstr "%s"
#define scchr "%c"
#define scflt "%f"
#define scdbl "%lf"
#define scnewl "\n"
using namespace std;
template <typename T>
inline void mie(T& curr, const T x) {
curr = min(x, curr);
}
template <typename T>
inline void mae(T& curr, const T x) {
curr = max(x, curr);
}
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<unsigned int> vi;
typedef vector<pii> vpii;
typedef vector<vi> matrix;
typedef unordered_set<int> usi;
typedef set<int> si;
typedef map<int, int> mii;
typedef map<int, usi> miusi;
typedef map<int, vi> mivi;
typedef map<int, si> misi;
typedef list<int> li;
typedef priority_queue<pii, vector<pii>, greater<pii>> dijk_queue;
/// @brief For the USACO freopen. Does filename.in and .out
inline void fopen(const string& filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
/// @brief My best attemp at making a universal coords to i. It dont care about anything.
inline int coordstoi(const int row, const int collumn, const int tot_col) {
return row * tot_col + collumn;
}
///@brief Reverse a segment from [start, stop]. Start and Stop are 0 Indexed
template <typename T>
inline void reverse(vector<T>& reverse, int start, int stop) {
const vector<T> old_rev = reverse;
while (start < stop) {
reverse[start] = old_rev[stop], reverse[stop] = old_rev[start];
++start, --stop;
}
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
fopen("diamond");
unsigned int n, k, l = 0, r = 0, ml=0, mr=0;
cin>>n>>k;
/*if (n <= 0) {
cout<<0;
exit(0);
}*/
vi diamonds(n);
for (size_t i = 0; i<n; ++i) {
cin>>diamonds[i];
}
sort(diamonds.begin(), diamonds.end());
for (; r < n; r++) {
if (diamonds[r] - diamonds[l] > k) {
if (mr-ml < r-l) {
mr = r;
ml = l;
}
while ((diamonds[r] - diamonds[l] > k)) {
++l;
}
}
}
if (mr-ml < r-l) {
mr = r;
ml = l;
}
auto lo = diamonds.begin(), hi = diamonds.begin();
advance(lo, ml), advance(hi, mr);
diamonds.erase(lo, hi);
unsigned int mml = 0, mmr = 0;
l = 0, r = 0;
n = diamonds.size();
for (; r < n; ++r) {
if (diamonds[r] - diamonds[l] > k) {
if (mmr-mml < r-l) {
mmr = r;
mml = l;
}
while (diamonds[r] - diamonds[l] > k) {
++l;
}
}
}
if (mmr-mml < r-l) {
mmr = r;
mml = l;
}
cout << (mr-ml) + (mmr - mml) << endl;
}
Basically, it takes the 2 pointer approach used in the bronze version, and runs it twice. It sorts array, finds biggest acceptable diamond set, stores length, erases, finds again, adds to old, outputs.