oj.uz

답안 #568144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568144 2022-05-24T17:15:43 Z alvingogo 카멜레온의 사랑 (JOI20_chameleon) C++14
40 / 100
 392 ms 344 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 392 ms 344 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 14 ms 208 KB Output is correct
11 Correct 16 ms 320 KB Output is correct
12 Correct 16 ms 320 KB Output is correct
13 Correct 17 ms 208 KB Output is correct
14 Correct 16 ms 208 KB Output is correct
15 Correct 17 ms 324 KB Output is correct
16 Correct 17 ms 320 KB Output is correct
17 Correct 19 ms 316 KB Output is correct
18 Correct 19 ms 336 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 384 ms 344 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 392 ms 344 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -