oj.uz

Submission #568142

# Submission time Handle Problem Language Result Execution time Memory
568142 2022-05-24T17:08:11 Z alvingogo Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 144 ms 340 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);

*/

void Solve(int N){
    int n=2*N;
    vector<vector<int> > v(n+1);
    vector<int> vis(n+1);
    vector<int> q(n);
    vector<pair<int,int> >ans;
    iota(q.begin(),q.end(),1);
    for(int i=1;i<=n;i++){
        vector<int> tmp;
        if(vis[i]){
            continue;
        }
        tmp.push_back(i);
        for(int j=i+1;j<=n;j++){
            if(vis[j]){
                continue;
            }
            tmp.push_back(j);
            if(Query(tmp)==1){
                int z=N-1;
                vector<int> p;
                for(int k=1;k<=n;k++){
                    if(k==i || k==j){
                        continue;
                    }
                    p.push_back(k);
                }
                if(Query(p)<N){
                    for(int k=1;k<=n;k++){
                        if(k==i || k==j){
                            continue;
                        }
                        vector<int> y;
                        for(int l=1;l<=n;l++){
                            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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 144 ms 340 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 7 ms 208 KB Output is correct
11 Correct 8 ms 208 KB Output is correct
12 Correct 7 ms 208 KB Output is correct
13 Correct 8 ms 208 KB Output is correct
14 Correct 8 ms 208 KB Output is correct
15 Correct 8 ms 336 KB Output is correct
16 Correct 8 ms 316 KB Output is correct
17 Correct 7 ms 208 KB Output is correct
18 Correct 8 ms 208 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 133 ms 336 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 144 ms 340 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -