Submission #978501

#	Time	Username	Problem	Language	Result	Execution time	Memory
978501		vjudge1	Team Contest (JOI22_team)	C++17	37 / 100	2100 ms	13300 KiB

team

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

int tt = 1, n;
ll x[200005], y[200005], z[200005];
pair<pair<ll, ll>, pair<ll, int>> p[200005];
vector<int> g1[3003], g2[3003], g3[3003];
ll mx;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x[i] >> y[i] >> z[i];
		p[i] = {{x[i], y[i]}, {z[i], i}};
	}
    if(n <= 4000){
        sort(p + 1, p + n + 1);
        for(int i = 3; i <= n; i++){
            set<ll> st;
            vector<pair<ll, ll>> v;
            for(int j = i - 1; j >= 1; j--){
                if(p[i].first.first != p[j].first.first)
                    v.push_back({p[j].first.second, j});
            }
            sort(v.begin(), v.end());
            // for(int j = 0; j < v.size(); j++){
            // 	if(j == 0) mx[j] = p[v[j].second].second.first;
            // 	else mx[j] = max(mx[j - 1], p[v[j].second].second.first);
            // }
            int last = 0;
            for(int j = 1; j < v.size(); j++){
                while(last < j && v[last].first != v[j].first){
                    st.insert(p[v[last].second].second.first);
                    last++;
                }
                if(!st.empty() && p[v[j].second].second.first < *st.rbegin() && v[j].first > p[i].first.second && p[i].second.first < *st.rbegin()){
                    mx = max(mx, p[i].first.first + v[j].first + *st.rbegin());
                    // cout << p[i].first.first << " " << v[j].first << " " << *st.rbegin() << "\n";
                }
            }
        }
        if(mx == 0) cout << -1;
        else cout << mx;
        return 0;
    }
    for(int i = 1; i <= n; i++){
        g1[x[i]].push_back(i);
        g2[y[i]].push_back(i);
        g3[z[i]].push_back(i);
    }
    for(ll i = 1; i <= 20; i++){
        for(ll j = 1; j <= 20; j++){
            // vector<ll> v;
            for(ll k = 1; k <= 20; k++){
                for(int to1 : g1[i]){
                    for(int to2 : g2[j]){
                        for(int to3 : g3[k]){
                            if(to1 == to2 || to2 == to3 || to1 == to3) continue;
                            vector<pair<ll, int>> v1, v2, v3;
                            v1.push_back({x[to1], 1});
                            v1.push_back({x[to2], 2});
                            v1.push_back({x[to3], 3});

                            v2.push_back({y[to1], 1});
                            v2.push_back({y[to2], 2});
                            v2.push_back({y[to3], 3});

                            v3.push_back({z[to1], 1});
                            v3.push_back({z[to2], 2});
                            v3.push_back({z[to3], 3});

                            sort(v1.rbegin(), v1.rend());
                            sort(v2.rbegin(), v2.rend());
                            sort(v3.rbegin(), v3.rend());

                            if(v1[0].first != v1[1].first && v2[0].first != v2[1].first && v3[0].first != v3[1].first && v1[0].second != v2[0].second && v1[0].second != v3[0].second && v2[0].second != v3[0].second)
						        mx = max(mx, i + j + k);
                        }
                    }
                }
            }
        }
    }
    if(mx == 0) cout << -1;
    else cout << mx;
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int j = 1; j < v.size(); j++){
      |                            ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27