### tusm851's blog

By tusm851, history, 4 weeks ago, ,

I was solving the problems under Edu section when I found that for this problem under Suffix Array lectures, my solution works fine for the second test case on VS Code.

But the same code gives runtime error on CF. I am also unable to decipher the diagnostic comment which came attached with my submission, On further inspection I found that for different versions of gcc compilers, my solution gave runtime error on different test cases.

I am completely perplexed and would be grateful if someone sheds some light on this behavior.

UPD1 : Attaching the error comment screenshot and removing link to my submission.

• 0

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by tusm851 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by tusm851 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by tusm851 (previous revision, new revision, compare).
 » 4 weeks ago, # |   +1 We cannot see your submission because it is from Edu section -- submissions there are not public, so apparently you should not share your code. Copy the diagnostic comment instead, maybe it will be enough to tell what's the problem.
•  » » 4 weeks ago, # ^ |   0 Oh sorry, I did not know that.I have removed the link to submission now. But won't you have to look at my code to figure out what's wrong? Also I have updated the blog where you can see the diagnostic comment.
•  » » » 4 weeks ago, # ^ |   +1 It seems like the problem occurs in line 256. Maybe you can just paste a part of your code.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Please go through this. I have commented the line 256 so that you may find it easily. Also, I have added comments for better readability. Spoiler#include #define MOD 1000000007 #define PR 998244353 #define INF INT_MAX #define endl "\n" #define mp make_pair #define mt make_tuple #define pb push_back #define ff first #define ss second #define vi vector #define vpi vector > #define shot(p) sort(p.begin(),p.end()) #define lli long long int #define sz(a) int((a).size()) #define form(i, l, r) for (i = l; i > r; --i) #define forl(i, l, r) for (i = l; i < r; ++i) using namespace std; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); lli t,b,c,q,h,i,j,k,n,n1,n2,n3,st,mid,end,ind,min1,min2,max1,max2,lsb,sum,tot,rem,ans,prod,diff,count,flag,flag1,temp,temp1,temp2; lli mod=1000000007, inf =LLONG_MAX , pr=998244353; for(t=1;t--;cout<>s1; forl(i,0,sz(s1)) s2.pb(0); s1=s1+s2; vector > v;lli a[sz(s1)]; forl(j,0,sz(s1)) { a[j]=s1[j]; } for(i=1;i(v[0]); a[temp1]=1; temp=1; forl(j,1,sz(s2)) { temp1=get<2> (v[j]); if(get<0>(v[j]) ==get<0>(v[j-1]) && get<1>(v[j]) ==get<1>(v[j-1])) { //cout<(v[j])<<" "<(v[j]); a[temp1]=temp; } else a[temp1]=++temp; } v.clear(); } vpi v1,v2; forl(j,0,sz(s2)) { v1.pb(mp(a[j],j)); v2.pb(mp(a[j],j)); } shot(v1); //cout<>b; forl(k,0,b) //This loop takes in b queries and does substring search for each of them { cin>>s2; st=0;end=sz(s1)/2-1;n1=-1;n2=-1; temp=sz(s1)/2; while(temp) //This loop finds the first occurence of the given substring (if it exists) { temp>>=1; mid=(st+end)/2; flag=0; forl(i,0,sz(s2)) { if(s1[v1[mid].ss+i]==s2[i]) {} else{ if(s1[v1[mid].ss+i]>s2[i]) end=mid-1; else st=mid+1; flag=1; break; } } if(flag==0) { n1=mid; end=mid-1; } } temp=sz(s1)/2; st=0;end=sz(s1)/2-1; while(temp) //This loop finds the last occurence of the given substring (if it exists) { temp>>=1; mid=(st+end)/2; flag=0; //if(st==end) ind=0; forl(i,0,sz(s2)) { //cout<s2[i]) end=mid-1; else st=mid+1; flag=1; break; } } if(flag==0) { n2=mid; st=mid+1; } } if(n1!=-1 && n2!=-1) { ans=n2-n1+1; //n1 is the first occurence and n2 is the last occuence cout<
•  » » » » » 4 weeks ago, # ^ |   0 All I can say is v2[i].ff happens to exceed the bounds of v1. For example, in the test a 1 a v2[i].ff = 97 but v1 has size 1.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Yes, my code does not work on this test case. Thanks, for showing me this. My solution got accepted after making the necessary changes.But, it still baffles me how the same code passes Test case 2 of the problem for C++17 and gets stuck at the same test case for C++11. It would be of immense help if you could explain me this phenomenon.
•  » » » » » » » 4 weeks ago, # ^ |   0 My guess is that it is optimization differences. Optimizations should be more advanced in C++17, so if the compiler sees that some part of the code does not influence the result (let's say, after some point whatever you do with eome variables, it is bot logically linked to the variables, used later, e.g. ones printed as answer), it just skips it entirely. But it is really hard to say for sure, at least for me.
•  » » » » » » » » 4 weeks ago, # ^ |   0 After seeing the results I think I should switch to C++17 as my default language.Nevertheless, thanks for your replies and your help.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by tusm851 (previous revision, new revision, compare).