Submission #965083

#	Time	Username	Problem	Language	Result	Execution time	Memory
965083		vjudge1	Jail (JOI22_jail)	C++17	0 / 100	1 ms	4556 KiB

jail

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define int ll
#define pii pair<int,int>
#define F first
#define S second
#define in insert
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz(s) (int)s.size()
#define ppb pop_back

const int MAX=2e5+10;
const int inf=1e18;

const int dx[4]={0,0,1,-1};
const int dy[4]={-1,1,0,0};

int n;
int ban[MAX];
int da[MAX],db[MAX],dc[MAX];
int x[MAX],y[MAX],z[MAX];
multiset<int> sx,sy,sz;
map<pii,vector<int>> mp1,mp2,mp3;

struct Sub1{
  vector<int> v1[10][10],v2[10][10],v3[10][10];
  void solve(){
    for(int i=1;i<=n;i++){
      sx.in(x[i]);
      sy.in(y[i]);
      sz.in(z[i]);
      v1[x[i]][y[i]].pb(i);
      v2[y[i]][z[i]].pb(i);
      v3[x[i]][z[i]].pb(i);
    }
    for(int f=1;f<=n;f++){
      if(sx.empty())break;
      int ma=*sx.rbegin();
      int mb=*sy.rbegin();
      int mc=*sz.rbegin();
      for(auto pos:v1[ma][mb]){
        if(!ban[pos]){
          sx.erase(sx.find(x[pos]));
          sy.erase(sy.find(y[pos]));
          sz.erase(sz.find(z[pos]));
        }
        ban[pos]=1;
      }
      for(auto pos:v2[mb][mc]){
        if(!ban[pos]){
          sx.erase(sx.find(x[pos]));
          sy.erase(sy.find(y[pos]));
          sz.erase(sz.find(z[pos]));       
        }
        ban[pos]=1;
      }
      for(auto pos:v3[ma][mc]){
        if(!ban[pos]){
          sx.erase(sx.find(x[pos]));
          sy.erase(sy.find(y[pos]));
          sz.erase(sz.find(z[pos]));
        }
        ban[pos]=1;
      }
      v1[ma][mb].clear();
      v2[mb][mc].clear();
      v3[ma][mc].clear();
    }
    vector<int> a,b,c;
    for(int i=1;i<=n;i++){
      if(!ban[i]){
        a.pb(x[i]);
        b.pb(y[i]);
        c.pb(z[i]);
      }
    }
    sort(all(a));
    sort(all(b));
    sort(all(c));
    if(sz(a)<3){
      cout<<-1<<"\n";
      return;
    }
    cout<<a.back()+b.back()+c.back()<<"\n";
  }
};

void solve(){
  vector<int> a,b,c;
  cin>>n;
  int mxa=0,mxb=0,mxc=0;
  for(int i=1;i<=n;i++){
    cin>>x[i]>>y[i]>>z[i];
    sx.in(x[i]);
    sy.in(y[i]);
    sz.in(z[i]);
    mxa=max(mxa,x[i]);
    mxb=max(mxb,y[i]);
    mxc=max(mxc,z[i]);
    mp1[{x[i],y[i]}].pb(i);
    mp2[{y[i],z[i]}].pb(i);
    mp3[{x[i],z[i]}].pb(i);
  }
  bool ok=(mxa<=5&&mxb<=5&&mxc<=5);
  // if(*sx.rbegin()<=5&&*sy.rbegin()<=5&&*sz.rbegin()<=5){
  //   Sub1 res;
  //   res.solve();
  //   return;
  // }
  for(int f=1;f<=n;f++){
    if(sx.empty())break;
    int ma=*sx.rbegin();
    int mb=*sy.rbegin();
    int mc=*sz.rbegin();
    if(mp1.count({ma,mb}))for(auto pos:mp1[{ma,mb}]){
      if(!ban[pos]){
        sx.erase(sx.find(x[pos]));
        sy.erase(sy.find(y[pos]));
        sz.erase(sz.find(z[pos]));
      }
      ban[pos]=1;
      if(ok)mp1[{ma,mb}].clear();
    }
    if(mp2.count({mb,mc}))for(auto pos:mp2[{mb,mc}]){
      if(!ban[pos]){
        sx.erase(sx.find(x[pos]));
        sy.erase(sy.find(y[pos]));
        sz.erase(sz.find(z[pos]));       
      }
      ban[pos]=1;
      if(ok)mp2[{mb,mc}].clear();
    }
    if(mp3.count({ma,mc})){
      for(auto pos:mp3[{ma,mc}]){
        if(!ban[pos]){
          sx.erase(sx.find(x[pos]));
          sy.erase(sy.find(y[pos]));
          sz.erase(sz.find(z[pos]));
        }
        ban[pos]=1;
      }
      if(ok)mp3[{ma,mc}].clear();
    }
  }
  for(int i=1;i<=n;i++){
    if(!ban[i]){
      a.pb(x[i]);
      b.pb(y[i]);
      c.pb(z[i]);
    }
  }
  sort(all(a));
  sort(all(b));
  sort(all(c));
  if(sz(a)<3){
    cout<<-1<<"\n";
    return;
  }
  cout<<a.back()+b.back()+c.back()<<"\n";
}

// 18 17 17 17 27 17 27 18 18 18 18 18 18 17 27 17 17 18 17 18 18 17 17 18 16 29 25 29 25 31 25 16 16 17 17 25 16 22 22 16 28 15 17 18 16 17 17 16 22 15 22 28 15 22 27 16 21 15 17 18 16 17 17 16 27 15 27 20 15 27 16 21 15 17 17 16 17 17 16 28 15 26 20 15 25 16 30 17 17 17 17 17 17 16 30 16 16 17 16 15 17 18 16 17 17 16 21 15 21 29 15 21 16 16 16 16 16 16 15 29 15 15 16 15 24 30 24 28 24 16 16 17 17 24 16 23 26 24 26 16 16 17 17 26 16 23 28 23 16 16 16 16 23 16 24 27 16 16 17 17 27 16 24 16 16 17 17 24 16 16 16 16 16 28 16 15 25 20 15 25 15 15 16 15 20 15 28 15 20 15 
// 18 17 17 17 27 17 27 18 18 18 18 18 18 17 27 17 17 18 17 18 18 17 17 18 16 29 25 29 25 31 25 16 16 17 17 25 16 22 22 16 28 15 17 18 16 17 17 16 22 15 22 28 15 22 27 16 21 15 17 18 16 17 17 16 27 15 27 20 15 27 16 21 15 17 17 16 17 17 16 28 15 26 20 15 25 16 30 17 17 17 17 17 17 16 30 16 16 17 16 15 17 18 16 17 17 16 21 15 21 29 15 21 16 16 16 16 16 16 15 29 15 15 16 15 24 30 24 28 24 16 16 17 17 24 16 23 26 24 26 16 16 17 17 26 16 23 28 23 16 16 16 16 23 16 24 27 16 16 17 17 27 16 24 16 16 17 17 24 16 16 16 16 16 28 16 15 25 20 15 25 15 15 16 15 20 15 28 15 20 15  

main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

jail.cpp:169:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  169 | main(){
      | ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23