oj.uz

Submission #235015

# Submission time Handle Problem Language Result Execution time Memory
235015 2020-05-26T17:57:19 Z rajarshi_basu Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 52 ms 504 KB 

#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define mp make_pair
#define vv vector
#define endl '\n'

#include "chameleon.h"

using namespace std;

bool query(vi all, int extra){
	all.pb(extra);
	return Query(all) == all.size();
}

int count(vi all, int extra){
	all.pb(extra);
	return ((int)all.size()) - Query(all);
}
int query3(int a,int b,int c){
	vi all;all.pb(a);all.pb(b);all.pb(c);
	return Query(all);
}

vi res;
bool ok = 1;
void binsrch(vi allNum,int x){
	if(allNum.size() == 1){
		res.pb(allNum[0]);
		return;
	}
	//cout << allNum.size() << endl;;
	vi halves[2];
	FOR(i,allNum.size())halves[i%2].pb(allNum[i]);
	if(query(halves[0],x)){
		binsrch(halves[1],x);
	}else{
		binsrch(halves[0],x);
		if(res.size() < 3 and !query(halves[1],x))binsrch(halves[1],x);
	}

	//FOR(j,2)if(!query(halves[j],x))binsrch(halves[j],x);
}
vi indsets[4];

void Solve(int n){
	n*=2;
	indsets[0].pb(1);
	FORE(i,2,n){
		FOR(j,4){
			if(indsets[j].empty() or query(indsets[j],i)){
				indsets[j].pb(i);
				break;
			}
		}
	}
	// everything has been partitioned.
	vi edges[n+1];
	FOR(i,4){
		for(auto e : indsets[i]){
			
			FOR(j,4){
				res.clear();
				if(i != j and !indsets[j].empty()){
					ok = 1;
					if(query(indsets[j],e))continue;
					binsrch(indsets[j],e);
					if(!res.empty())for(auto x:res)edges[e].pb(x);
				}
			}
		}
	}
	
	FORE(i,1,n){
	//	cout << edges[i].size() << endl;
	}
	set<int> allSets[n+1];
	FOR(i,n+1)for(auto x:edges[i])allSets[i].insert(x);
	FORE(i,1,n){

		if(edges[i].size() == 1){
			continue;
		}
		//if(edges[i].size() != 3)while(1);
		// has 3 edges;
		int a = query3(i,edges[i][0],edges[i][1]);
		int b = query3(i,edges[i][1],edges[i][2]);
		int numTorem;
		if(a == 1){
			numTorem = edges[i][2];
		}else if(b == 1){
			numTorem = edges[i][0];
		}else{
			numTorem = edges[i][1];
		}
		allSets[i].erase(numTorem);
		allSets[numTorem].erase(i);
	}
	FORE(i,1,n){
		int x = *(allSets[i].begin());
		if(i < x)Answer(i,x);
	}
}

Compilation message

chameleon.cpp: In function 'bool query(std::vector<int>, int)':
chameleon.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return Query(all) == all.size();
         ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp: In function 'void binsrch(std::vector<int>, int)':
chameleon.cpp:18:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
chameleon.cpp:62:6:
  FOR(i,allNum.size())halves[i%2].pb(allNum[i]);
      ~~~~~~~~~~~~~~~           
chameleon.cpp:62:2: note: in expansion of macro 'FOR'
  FOR(i,allNum.size())halves[i%2].pb(allNum[i]);
  ^~~

Subtask #1
4.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 Correct 49 ms 504 KB Output is correct
4 Correct 49 ms 504 KB Output is correct
5 Correct 50 ms 504 KB Output is correct
6 Correct 49 ms 504 KB Output is correct
7 Correct 52 ms 504 KB Output is correct
8 Correct 49 ms 504 KB Output is correct
9 Correct 49 ms 504 KB Output is correct

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 5 ms 384 KB Output is correct
7 Correct 5 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 5 ms 384 KB Output is correct
7 Correct 5 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 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 8 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 Incorrect 47 ms 384 KB Wrong Answer [3]
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 Correct 49 ms 504 KB Output is correct
4 Correct 49 ms 504 KB Output is correct
5 Correct 50 ms 504 KB Output is correct
6 Correct 49 ms 504 KB Output is correct
7 Correct 52 ms 504 KB Output is correct
8 Correct 49 ms 504 KB Output is correct
9 Correct 49 ms 504 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 8 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Incorrect 47 ms 384 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -