oj.uz

Submission #234856

# Submission time Handle Problem Language Result Execution time Memory
234856 2020-05-26T05:38:00 Z anayk Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 8 ms 640 KB 
#include "chameleon.h"
#include <set>
#include <vector>

std::set<int> Adj[501];
std::vector<int> edges[501];
std::vector<int> groups[4];
int part[501];

int check(int x, int y) {
  return (y != x + 1);
}

int threeQuery(int x, int y, int z) {
  std::vector<int> q;
  q.push_back(x);
  q.push_back(y);
  q.push_back(z);
  return Query(q);
}

int queryRange(int l, int r, int group) {
  if(l == r)
    return 1;

  std::vector<int> q;
  for(int i = l; i <= r; i++)
    q.push_back(groups[group][i]);

  return Query(q);
}

int queryRange(int l, int r, int x, int group) {
  std::vector<int> q;
  for(int i = l; i <= r; i++)
    q.push_back(groups[group][i]);
  q.push_back(x);
  return Query(q);
}

void bs(int x, int l, int r, int group) {
  if(l == r) {
    Adj[x].insert(groups[group][l]);
    Adj[groups[group][l]].insert(x);
    return;
  }

  int m = (l+r)/2;
  if(check(queryRange(l, m, group), queryRange(l, m, x, group)))
    bs(x, l, m, group);
  if(check(queryRange(m+1, r, group), queryRange(m+1, r, x, group)))
    bs(x, m+1, r, group);
}
  
void Solve(int N) {
  for(int i = 0; i < 4; i++) {
    groups[i].push_back(i+1);
    part[i+1] = i;
  }

  for(int i = 5; i <= 2*N; i++) {
    for(int j = 0; j < 4; j++) {
      groups[j].push_back(i);
      if(Query(groups[j]) == groups[j].size()) {
        part[i] = j;
        break;
      }
      else
        groups[j].pop_back();
    }
  }

  for(int i = 1; i <= 2*N; i++) {
    for(int j = part[i]+1; j < 4; j++) {
      if(check(queryRange(0, groups[j].size()-1, j), queryRange(0, groups[j].size()-1, i, j)))
        bs(i, 0, groups[j].size()-1, j);
    }
  }

  for(int i = 1; i <= 2*N; i++) {
    if(Adj[i].size() == 3) {
      for(std::set<int>::iterator it = Adj[i].begin(); it != Adj[i].end(); it++) {
        edges[i].push_back(*it);
      }
    }
  }
  
  for(int i = 1; i <= 2*N; i++) {
    if(edges[i].size() == 3) {
      int x0 = threeQuery(i, edges[i][1], edges[i][2]);
      int x1 = threeQuery(i, edges[i][0], edges[i][2]);

      int x;
      if(x0 == 1)
        x = edges[i][0];
      else if(x1 == 1)
        x = edges[i][1];
      else
        x = edges[i][2];

      Adj[x].erase(i);
      Adj[i].erase(x);
    }
  }

  for(int i = 1; i <= 2*N; i++) {
    int j = *Adj[i].begin();
    if(i < j)
      Answer(i, j);
  }
}

Compilation message

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(Query(groups[j]) == groups[j].size()) {
          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -