oj.uz

Submission #944071

# Submission time Handle Problem Language Result Execution time Memory
944071 2024-03-12T08:04:41 Z WongYiKai Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 17 ms 464 KB 
#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;
typedef int ll;

void Solve(int N) {
  
  vector<ll> pa[2*N+5];
  for (int i=1;i<=2*N;i++){
	  for (int j=i+1;j<=2*N;j++){
		  vector<ll> temp(2);
		  temp[0] = i;
		  temp[1] = j;
		  if (Query(temp)==1) {
			  pa[i].push_back(j);
			  pa[j].push_back(i);
		  }
	  }
  }
  ll col[2*N+5];
  ll know[2*N+5];
  memset(know,0,sizeof(know));
  for (int i=1;i<=2*N;i++){
	  if (know[i]==1) continue;
	  if (pa[i].size()==1){
		  col[i] = pa[i][0];
		  col[pa[i][0]] = i;
		  know[i] = 1;
		  know[pa[i][0]] = 1;
		  continue;
	  }
	  ll like=-1;
	  vector<ll> temp(3);
	  temp[0] = i;
	  temp[1] = pa[i][0];
	  temp[2] = pa[i][1];
	  if (Query(temp)==1){
		  like = 2;
	  }
	  temp[1] = pa[i][1];
	  temp[2] = pa[i][2];
	  if (Query(temp)==1){
		  like = 0;
	  }
	  temp[1] = pa[i][2];
	  temp[2] = pa[i][0];
	  if (Query(temp)==1){
		  like = 1;
	  }
	  //cout << i << " " << pa[i][like] << "\n";
	  ll fail=-1,pass=-1;
	  for (int j=0;j<3;j++){
		  if (j==like) continue;
		  ll x = pa[i][j];
		  if (know[x]==1) {
			  fail=j;
			  break;
		  }
		  if (pa[x].size()==1){
			  if (pa[x][0]==i){
				  pass=j;
				  break;
			  }
			  else{
				  fail=j;
				  break;
			  }
		  }
		  ll like2=-1;
		  vector<ll> temp2(3);
		  temp2[0] = x;
		  temp2[1] = pa[x][0];
		  temp2[2] = pa[x][1];
		  if (Query(temp2)==1){
			  like2 = 2;
		  }
		  temp2[1] = pa[x][1];
		  temp2[2] = pa[x][2];
		  if (Query(temp2)==1){
			  like2 = 0;
		  }
		  temp2[1] = pa[x][2];
		  temp2[2] = pa[x][0];
		  if (Query(temp2)==1){
			  like2 = 1;
		  }
		  //cout << x << " " << pa[x][like2] << "\n";
		  if (pa[x][like2]==i){
			  fail=j;
			  break;
		  }
		  else{
			  pass=j;
			  break;
		  }
	  }
	  //cout << i << " " << fail << " " << pass << "\n";
	  if (fail==-1){
		  col[i] = pa[i][pass];
		  col[pa[i][pass]] = i;
		  know[i] = 1;
		  know[pa[i][pass]] = 1;
	  }
	  else{
		  for (int j=0;j<3;j++){
			  if (j==like || j==fail) continue;
			  col[i] = pa[i][j];
			  col[pa[i][j]] = i;
			  know[i] = 1;
			  know[pa[i][j]] = 1;
		  }
	  }
  }
  ll out[2*N+5];
  memset(out,0,sizeof(out));
  for (int i = 1; i <= 2*N; i++) {
	  if (out[i]==1) continue;
	  //cout << i << " " << col[i] << "\n";
	  Answer(i,col[i]);
	  out[i]=1;
	  out[col[i]]=1;
  }
}

Subtask #1
0 / 4.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 15 ms 348 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 17 ms 464 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -