11920 - 0 s, 1 s and ? Marks

Moderator: Board moderators

New poster
Posts: 1
Joined: Tue Feb 24, 2015 3:44 pm

Re: 11920 - 0 s, 1 s and ? Marks

Brianfry, can you check it again. It is still getting TLE.

Code: Select all

``````#pragma comment(linker,"/STACK:16777216")
#pragma  warning ( disable: 4786)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<queue>
#include<sstream>
#include<stack>
#include<list>
#include <bitset>
#include<iomanip>
#include <fstream>
#include<ctime>

using namespace std;

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

#define MX 1000000

#define forl(i,a,b) for ( i = a; i < b; i++)
#define fore(i,a,b) for ( i = a; i <= b; i++)
#define forrev(i,a,b) for ( i = a; i >= b; i--)
#define pb push_back
typedef long long  LL;
#define in(a,b,c) ((a) <= (b) && (b) <= (c))
#define ms(a,b) memset((a),(b),sizeof(a))

#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ull unsigned long long int
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

string to_string(long long x) { stringstream ss; ss << x; return ss.str(); }
long long to_int(const string &s) { stringstream ss; ss << s; long long x; ss >> x; return x; }

int max_group;
int ans;
char in[1002];
int n;
void max_optimum_group()
{
int cnt=0;
int i;
max_group = 1;
bool ques = true;
forl(i,0,n)
{

if(in[i] == '?')
{
ques = true;
if(cnt > 0)
{
max_group = max(max_group,cnt);
}
}
else
{
if(i>0 && in[i] == in[i-1])
{
cnt++;
}
else
{
max_group = max(max_group,cnt);
cnt=1;
}
}
}
max_group = max(max_group,cnt);

}
void doit(int pos, int max_group_size, int curr_size, char prev)
{
int i,j,k,sz;
if(pos == n)
{
max_group_size = max(max_group_size, curr_size);
ans = min(ans,max_group_size);
return;
}
if(max_group_size > ans)
return;
if(curr_size >= max_group)
return;
if(in[pos] != '?')
{
if(in[pos] == prev)
{
i = pos;
sz = curr_size;
while(i<n && in[i] == prev)
{
i++;
sz++;
}
doit(i,max_group_size,sz,prev);
}
else
{
max_group_size = max(max_group_size,curr_size);
i = pos;
sz = 0;
while(i<n && (in[i] != '?') && in[i] != in[pos])
{
sz++;
i++;
}
doit(i,max_group_size,sz,in[pos]);
}

}
else
{
char arr[2];
int ind=0;
if(pos != 0)
{

int used = (prev-'0')^1;
char c1 = char('0'+used);
//max_group_size = max(max_group_size,curr_size);
arr[ind] = c1;
ind++;
}
if(pos + 1 < n && in[pos+1] != '?' && in[pos+1] != prev)
{
int c1 = in[pos+1] - '0';
c1 = c1^1;
arr[ind] = char('0' + c1);
ind++;
}
if(pos + 1 < n && in[pos+1] != '?' && in[pos+1] == prev)
{
doit(pos+1,max_group_size,1,(prev-'0')^1);
return;
}
if(ind == 0)
{
arr[0] = '0';
arr[1] = '1';
}
if(ind == 1)
{
arr[1] = char('0' + ((arr[0]-'0')^(1)));
}
if(arr[0] == prev)
{
if(max_group_size < ans)
doit(pos+1,max_group_size,curr_size+1,arr[0]);
}
else
{
max_group_size = max(max_group_size,curr_size);
if(max_group_size < ans)
doit(pos+1,max_group_size,1,arr[0]);
}

if(arr[1] == prev)
{
if(max_group_size < ans)
doit(pos+1,max_group_size,curr_size+1,arr[1]);
}
else
{
max_group_size = max(max_group_size,curr_size);
if(max_group_size < ans)
doit(pos+1,max_group_size,1,arr[1]);
}
}
}
int main()
{
int t;
scanf("%d",&t);
getchar();
int ca = 1;
while(t--)
{
gets(in);
n = strlen(in);
max_optimum_group();
ans = max_group;
//cout << max_group << endl;
doit(0, 0, 0, '-');

printf("Case %d: %d\n",ca++,ans);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11920 - 0 s, 1 s and ? Marks

Your algorithm is wrong. Try input:

Code: Select all

``````1
0?1``````
AC output 2
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA