Solution for CodeForces 733D - Kostya the Sculptor

Solution #

WLOG, assume $a\leq b\leq c$ . If we choose only one stone, the diameter of the sphere is $\frac a 2$ . If we want to choose two stones, we should find another stone whose two of its edges are $b$ and $c$ , since we must expand the shortest side to get a bigger sphere. We can use a set to maintain the length of the edge and the index.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename... Args>
void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
    cin>>n;
    vector<int> ans;
    int best=0;
    map<pii,pii> mp;
    for1(i,n){
        int a[3];
        forn(i,3) cin>>a[i];
        sort(a,a+3);
        if(a[0]>best){
            ans={i};
            best=a[0];
        }
        if(mp.count({a[1],a[2]})){
            auto p=mp[{a[1],a[2]}];
            int now=min({a[1],a[2],a[0]+p.F});
            if(now>best){
                best=now;
                ans={i,p.S};
            }
        }
        mp[{a[0],a[1]}]=max(mp[{a[0],a[1]}],{a[2],i});
        mp[{a[0],a[2]}]=max(mp[{a[0],a[2]}],{a[1],i});
        mp[{a[1],a[2]}]=max(mp[{a[1],a[2]}],{a[0],i});
    }
    cout<<ans.size()<<endl;
    for(auto it:ans) cout<<it<<' ';
    return 0;
}