제출 #218218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218218		TheLorax	함박 스테이크 (JOI20_hamburg)	C++11	15 / 100	3076 ms	70296 KiB

hamburg

#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LBS 20
#define MOD ((long long)1e9+7) //1e9+9
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}

using namespace std;

typedef long long ll;
typedef double rat;
typedef long long bi;
typedef pair<ll, ll> ii;
typedef std::vector<ii> vii;
typedef std::map<ll, ll> mii;
typedef bitset<LBS> bis;
typedef std::vector<bis> vbs;
typedef priority_queue<ii, std::vector<ii>, greater<ii> > minpq;
typedef priority_queue<ii, std::vector<ii>, less<ii> > maxpq;
typedef priority_queue<ii> pq;

struct ham{
  ll l, d, r, u;
};

template<class T>
void in(T &a){
  for(auto &x: a)
    cin >> x;
}

template<class T>
void out(T &a, string sep=" "){
  for(auto x: a)
    cout << x<<sep;
  cout << '\n';
}

template<class T>
void err(T &a, string sep=" "){
  for(auto x: a)
    cerr << x <<sep;
  cerr << '\n';
}

std::vector<ham> h;
std::vector<int> ma;
std::vector<ii> ou;
int n, k;

void end(){
  for(auto &x: ou)
    cout << x.F<<" "<<x.S<<"\n";
  exit(0);
}

template<class T>
void pop(T &pq){
  while (!pq.empty() && ma[pq.top().S])
    pq.pop();
  if(pq.empty())
    end();
}

void rek(minpq pqxi, maxpq pqxa, minpq pqyi, maxpq pqya, int idx=0){
  pop(pqxi);
  pop(pqxa);
  pop(pqyi);
  pop(pqya);
  if(idx==k)
    return;
  ll xmi=pqxi.top().F;
  ll xma=pqxa.top().F;
  ll ymi=pqyi.top().F;
  ll yma=pqya.top().F;
  // if(xmi>=xma || ymi>=yma){
  //   ou[idx]={xmi,ymi};
  //   for(int i=0; i<n; i++)
  //     if(h[i].l<=xmi && xmi<=h[i].r && h[i].d<=ymi && ymi<=h[i].u)
  //       ma[i]++;
  //   rek(pqxi, pqxa, pqyi, pqya, idx+1);
  //   for(int i=0; i<n; i++)
  //     if(h[i].l<=xmi && xmi<=h[i].r && h[i].d<=ymi && ymi<=h[i].u)
  //       ma[i]--;
  //
  // }
  for(auto &c: {MP(xmi,ymi),MP(xmi,yma),MP(xma,ymi),MP(xma,yma)}){
    // std::cerr << c.F<<" "<<c.S << '\n';
    ou[idx]=c;
    for(int i=0; i<n; i++)
      if(h[i].l<=c.F && c.F<=h[i].r && h[i].d<=c.S && c.S<=h[i].u)
        ma[i]++;
    rek(pqxi, pqxa, pqyi, pqya, idx+1);
    for(int i=0; i<n; i++)
      if(h[i].l<=c.F && c.F<=h[i].r && h[i].d<=c.S && c.S<=h[i].u)
        ma[i]--;
  }
  if(idx==0 && k==4){
    for(int i=0; i<n; i++){
      assert(!ma[i]);
      if(h[i].l<=xmi && xmi<=h[i].r){
        for(auto &c: {MP(xmi,h[i].d),MP(xmi,h[i].u)}){
          // std::cerr << c.F<<" "<<c.S << '\n';
          ou[idx]=c;
          for(int i=0; i<n; i++)
            if(h[i].l<=c.F && c.F<=h[i].r && h[i].d<=c.S && c.S<=h[i].u)
              ma[i]++;
          rek(pqxi, pqxa, pqyi, pqya, idx+1);
          for(int i=0; i<n; i++)
            if(h[i].l<=c.F && c.F<=h[i].r && h[i].d<=c.S && c.S<=h[i].u)
              ma[i]--;
        }
      }
    }
    end();
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  minpq pqxi, pqyi;
  maxpq pqxa, pqya;
  h.resize(n);
  ou.resize(k,{1,1});
  ma.resize(n,0);
  for(int i=0; i<n; i++){
    cin >> h[i].l>>h[i].d>>h[i].r>>h[i].u;
    pqxi.emplace(h[i].r,i);
    pqxa.emplace(h[i].l,i);
    pqyi.emplace(h[i].u,i);
    pqya.emplace(h[i].d,i);
  }
  rek(pqxi, pqxa, pqyi, pqya);
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79