제출 #568144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568144		alvingogo	Chameleon's Love (JOI20_chameleon)	C++14	40 / 100	392 ms	344 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

/*
int Query(const std::vector<int> &p);
void Answer(int a, int b);

*/
mt19937 rnd(time(NULL));
void Solve(int N){
    int n=2*N;
    vector<vector<int> > v(n+1);
    vector<int> vis(n+1);
    vector<int> h(n);
    iota(h.begin(),h.end(),1);
    random_shuffle(h.begin(),h.end());
    vector<pair<int,int> > ans;
    for(int a=0;a<n;a++){
        int i=h[a];
        vector<int> tmp;
        if(vis[i]){
            continue;
        }
        tmp.push_back(i);
        for(int b=a+1;b<n;b++){
            int j=h[b];
            if(vis[j]){
                continue;
            }
            tmp.push_back(j);
            if(Query(tmp)==1){
                int z=N-1;
                vector<int> p;
                for(int c=0;c<n;c++){
                    int k=h[c];
                    if(k==i || k==j){
                        continue;
                    }
                    p.push_back(k);
                }
                if(Query(p)<N){
                    for(int c=0;c<n;c++){
                        int k=h[c];
                        if(k==i || k==j){
                            continue;
                        }
                        vector<int> pp=h;
                        vector<int> y;
                        random_shuffle(pp.begin(),pp.end());
                        for(int d=0;d<n;d++){
                            int l=pp[d];
                            if(l==i || l==j || l==k){
                                continue;
                            }
                            y.push_back(l);
                        }
                        z=max(z,Query(y));
                        if(z==N){
                            break;
                        }
                    }
                    if(z<N){
                        ans.push_back({i,j});
                        vis[i]=vis[j]=1;
                        break;
                    }
                }
                /*
                else{
                    ans.push_back({i,j});
                    vis[i]=vis[j]=1;
                    break;
                }
                */
            }
            tmp.pop_back();
        }
    }
    for(auto h:ans){
        Answer(h.fs,h.sc);
    }
}

/*
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;

constexpr int Q_MAX = 20'000;
constexpr int N_MAX = 500;

int N;
int Y[N_MAX * 2 + 1], C[N_MAX * 2 + 1], L[N_MAX * 2 + 1];

int query_count = 0;
int answer_count = 0;
bool finishes[N_MAX * 2 + 1];

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}


int Query(const std::vector<int> &p) {
  if (++query_count > Q_MAX) WrongAnswer(3);
  bool presents[N_MAX * 2 + 1];
  for (int i = 1; i <= N * 2; ++i) presents[i] = false;
  for (const int k : p) {
    if (k <= 0 || k > N * 2) WrongAnswer(1);
    if (presents[k]) WrongAnswer(2);
    presents[k] = true;
  }
  bool colors[N_MAX + 1];
  for (int j = 1; j <= N; ++j) colors[j] = false;
  int color_count = 0;
  for (int i = 1; i <= N * 2; ++i) {
    if (!presents[i]) continue;
    const int color = presents[L[i]] ? C[L[i]] : C[i];
    if (!colors[color]) {
      ++color_count;
      colors[color] = true;
    }
  }
  return color_count;
}

void Answer(int a, int b) {
  ++answer_count;
  cout << a << " " << b << "\n";
  if (a <= 0 || a > N * 2) WrongAnswer(4);
  if (b <= 0 || b > N * 2) WrongAnswer(4);
  if (finishes[a]) WrongAnswer(5);
  finishes[a] = true;
  if (finishes[b]) WrongAnswer(5);
  finishes[b] = true;
  if (C[a] != C[b]) WrongAnswer(6);
}

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  for (int i = 1; i <= N * 2; ++i) {
    if (scanf("%d", &Y[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * 2; ++i) {
    if (scanf("%d", &C[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * 2; ++i) {
    if (scanf("%d", &L[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * 2; ++i) finishes[i] = false;
  Solve(N);
  if (answer_count != N) WrongAnswer(7);
  printf("Accepted: %d\n", query_count);
  return 0;
}
*/

• Subtask 1: 0 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36