Submission #1170997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170997		Piokemon	Meetings (JOI19_meetings)	C++20	29 / 100	900 ms	1480 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

void rozw(vector<int> a){
  if (a.size()<=1) return;
  int split = a[rand()%(a.size()-1)+1];
  int v=a[0];
  //for (int x:a) cerr << x << ' ';
  //cerr << " A\n";
  vector<int> b,c; // b- czesc z v
  for (int y=1;y<a.size();y++){
    if (a[y]==split)continue;
    if (v==a[y]){
      b.push_back(v);
      continue;
    }
    int temp = Query(split,v,a[y]);
    //cerr << split << ' ' << v << ' ' << a[y] << ' ' << temp << " b\n";
    if (temp != v && temp!=split){
      b.push_back(a[y]);
      v=temp;
      //y=-1;
    }
    else{
      if (temp==v)b.push_back(a[y]);
      else c.push_back(a[y]);
    }
  }
  b.push_back(a[0]);
  c.push_back(split);
  //cerr << "bridge " << split << ' ' << v << '\n';
  Bridge(min(split,v),max(split,v));
  //for (int x:b) cerr << x << ' ';
  //cerr << " B\n";
  //for (int x:c) cerr << x << ' ';
  //cerr << " C\n";
  rozw(b);
  rozw(c);
}

void Solve(int N) {
  srand(N*3+14);
  vector<int>a;
  for (int x=0;x<N;x++)a.push_back(x);
  rozw(a);
  return;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71