oj.uz

Submission #283101

# Submission time Handle Problem Language Result Execution time Memory
283101 2020-08-25T10:00:30 Z kshitij_sodani Hidden Sequence (info1cup18_hidden) C++14
87 / 100
 98 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second


#include "grader.h"
//#define  ask isSubsequence
int st=0;
bool ask(vector<int> kk){
/*	if(st){
		for(int i=0;i<kk.size();i++){
			kk[i]=1-kk[i];
		}
	}*/
	return isSubsequence(kk);
}
vector <int> findSequence (int n){
   	vector<int> ans;

	vector<int> kk;

   	for(int i=0;i<(n+1)/2;i++){
   		kk.pb(1);
   	}
   	st=0;
   	if(ask(kk)){
   		st=0;
   		//0 in minority
   	}
   	else{
   		st=1;
   		//1 in minority
   	}
   	vector<int> ii;
   	for(int i=0;i<n/2;i++){
   		ii.pb(st);
   		if(ask(ii)){
   			continue;
   		}
   		else{
   			ii.pop_back();
   			break;
   		}
   	}
   	if(ii.size()==0){
   		for(int i=0;i<n;i++){
   			ans.pb(1-st);
   		}
   		return ans;
   	}
   	int le=n-ii.size();
   	int ind=-1;
   	vector<int> co;
   	for(int i=0;i<ii.size()+1;i++){
   		co.pb(0);
   	}
   	for(int i=0;i<ii.size();i++){
   		vector<int> cc;
   		for(int j=0;j<=i;j++){
   			cc.pb(st);
   		}
   		while(cc.size()<n/2+1){
   			cc.pb(1-st);
   		}
   		if(ask(cc)){
   			vector<int> dd;
   			for(int j=i;j<ii.size();j++){
   				dd.pb(st);
   			}

   			while(true){
   				dd.pb(1-st);
   				reverse(dd.begin(),dd.end());
   				
 
   				if(ask(dd)){
   					co[i]+=1;
   					reverse(dd.begin(),dd.end());
   					continue;
   				}
   				else{
   					break;
   				}
   			}
   			co[i]=le-co[i];


   		}
   		else{
   			vector<int> dd;
   			for(int j=0;j<=i;j++){
   				dd.pb(st);
   			}
   			while(dd.size()<n/2+1){
   				dd.pb(1-st);
   				if(ask(dd)){
   					co[i]+=1;
   					continue;
   				}
   				else{
   					break;
   				}
   			}


   		}
   	}
   	for(int i=0;i<le-co[0];i++){
   		ans.pb(1-st);
   	}
   	for(int j=0;j<ii.size();j++){
   		ans.pb(st);
   		int kk=co[j];
   		if(j==ii.size()-1){

   		}
   		else{
   			kk-=co[j+1];
   		}
   		for(int jj=0;jj<kk;jj++){
   			ans.pb(1-st);
   		}
   	}


/*



   	for(int i=0;i<ii.size()+1;i++){
   		vector<int> cc;
   		for(int j=0;j<i;j++){
   			cc.pb(st);
   		}
   		for(int k=1;k<=(le/2)+1;k++){
   			vector<int> dd=cc;
   			for(int j=0;j<k;j++){
   				dd.pb(1-st);
   			}
   			for(int j=i;j<ii.size();j++){
   				dd.pb(st);
   			}
   			if(ask(dd)){
   				co[i]+=1;
   				if(k==(le/2)+1){
   					ind=i;
   					break;
   				}
   			}
   			else{
   				break;
   			}

   		}
   	}
   	int su=ii.size();
   	for(auto i:co){
   		su+=i;
   	}
   	if(ind>=-1){
   		co[ind]+=(n-su);
   	}
   	for(int i=0;i<ii.size();i++){
   		for(int j=0;j<co[i];j++){
   			ans.pb(1-st);
   		}
   		ans.pb(st);
   	}
   	for(int j=0;j<co.back();j++){
   		ans.pb(1-st);
   	}*/
 /*  	for(auto j:co){
   		cout<<j<<":";
   	}
   	cout<<endl;
   	cout<<ii.size()<<endl;
   	*/

/*
   	for(auto j:co){
   		cout<<j<<":";
   	}
   	cout<<endl;
*/


   










    return ans;
}

Compilation message

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<ii.size()+1;i++){
      |                 ~^~~~~~~~~~~~
hidden.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<ii.size();i++){
      |                 ~^~~~~~~~~~
hidden.cpp:66:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |      while(cc.size()<n/2+1){
      |            ~~~~~~~~~^~~~~~
hidden.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |       for(int j=i;j<ii.size();j++){
      |                   ~^~~~~~~~~~
hidden.cpp:98:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |       while(dd.size()<n/2+1){
      |             ~~~~~~~~~^~~~~~
hidden.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int j=0;j<ii.size();j++){
      |                 ~^~~~~~~~~~
hidden.cpp:118:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |      if(j==ii.size()-1){
      |         ~^~~~~~~~~~~~~
hidden.cpp:56:9: warning: unused variable 'ind' [-Wunused-variable]
   56 |     int ind=-1;
      |         ^~~
grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   28 |     fprintf (fifo_out, "%d\n", ans.size ());
      |                         ~^     ~~~~~~~~~~~
      |                          |              |
      |                          int            std::vector<int>::size_type {aka long unsigned int}
      |                         %ld
grader.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<ans.size () && i < N; i++)
      |                   ~^~~~~~~~~~~~

Subtask #1
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 5
2 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 6
3 Correct 1 ms 256 KB Output is correct: Maximum length of a query = 5
4 Correct 0 ms 256 KB Output is correct: Maximum length of a query = 5
5 Partially correct 1 ms 256 KB Output is partially correct: Maximum length of a query = 5

Subtask #2
72.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 46 ms 256 KB Output is partially correct: Maximum length of a query = 84
2 Correct 52 ms 256 KB Output is correct: Maximum length of a query = 90
3 Correct 73 ms 256 KB Output is correct: Maximum length of a query = 96
4 Correct 31 ms 256 KB Output is correct: Maximum length of a query = 77
5 Correct 51 ms 256 KB Output is correct: Maximum length of a query = 95
6 Correct 12 ms 256 KB Output is correct: Maximum length of a query = 87
7 Correct 56 ms 256 KB Output is correct: Maximum length of a query = 97
8 Correct 33 ms 256 KB Output is correct: Maximum length of a query = 83
9 Correct 98 ms 256 KB Output is correct: Maximum length of a query = 101
10 Partially correct 73 ms 256 KB Output is partially correct: Maximum length of a query = 101
11 Correct 72 ms 256 KB Output is correct: Maximum length of a query = 96
12 Partially correct 7 ms 256 KB Output is partially correct: Maximum length of a query = 101
13 Correct 67 ms 256 KB Output is correct: Maximum length of a query = 101