Submission #155881

#	Time	Username	Problem	Language	Result	Execution time	Memory
155881		MvC	Martian DNA (IOI16_dna)	C++11	100 / 100	17 ms	504 KiB

dna

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "dna.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int i,l,r,mid,cnt;
string zr,on,rs;
string get(int l,int r,string x)
{
	string y="";
	for(int i=l;i<=r;i++)y+=x[i];
	return y;
}
string analyse(int n,int t)
{
	for(i=1;i<=n;i++)
	{
		on+='1';
		zr+='0';
	}
	l=0,r=n;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(make_test(get(0,mid-1,on)))l=mid+1;
		else r=mid-1;
	}
	l--;
	if(!l)return zr;
	if(l==n)return on;
	rs=get(0,l-1,on);
	for(i=1;i<=n;i++)
	{
		rs+='0';
		if(make_test(rs))cnt=0;
		else
		{
			rs.back()='1';
			cnt++;
			if(cnt>l)break;
		}
	}
	l=0,r=rs.size()-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(make_test(get(0,mid,rs)))l=mid+1;
		else r=mid-1;
	}
	l--;
	rs=get(0,l,rs);
	while(rs.size()<n)
	{
		rs='0'+rs;
		if(!make_test(rs))rs[0]='1';
	}
	return rs;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
	return 0;
}*/

Compilation message (stderr)

dna.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
dna.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(rs.size()<n)
        ~~~~~~~~~^~
grader.cpp: In function 'bool make_test(std::__cxx11::string)':
grader.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) {
                  ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= ss.size(); i++) {
                  ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pr[i] == p.size()) {

• Subtask 1: 11 / 11
• Subtask 2: 25 / 25
• Subtask 3: 64 / 64