yeah , in start i was solving it like that , and realized that it is very hard. but then saw that numbers are distinct.
There were some edge cases but you have 10 days to solve. I think its okay to have an ugly problem in a 10-day long contest(not only implementation wise).
There was nothing to learn
This was intended to be the first problem of div 1. We can’t put something beginners don’t even know of. Also these kind of ugly problems can be attempted by both beginners as well as experienced ones without any knowledge of fancy DS.
I have seen some uglier problems in past that might frustrate people for a long time but that teaches you to write neat codes for debugging later(rather than just making your code ugly too by handling tens of cases separately and praying your submission somehow passes) and improves observation skill as well.
I’ll not put this problem in a short contest but it can arguably fit in a long contest.
10 Likes
Thank you!!!
1 Like
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define F first
#define S second
#define pb push_back
#define po pop_back
#define f(i,n) for(ll i = 0; i < n; i++)
ll mod = 1e9+7;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t; cin>>t;
while(t--)
{
ll n; cin>>n;
ll a[n];
f(i,n) cin>>a[i];
ll q;
cin>>q;
while(q--)
{
ll r;
cin>>r;
ll sum = 0;
if(a[0] == 1)
{
if((r+n-1)/n != 1 && r%n == 1)
{
cout<<((r+n-1)/n -1)<<endl;
}
else
cout<<(r+n-1)/n<<endl;
continue;
}
if(a[n-1] == 1)
{
f(i,r)
{
sum += a[i%n];
if(i != r-1 && (a[i%n]%2 == 1) && (i%n != n-1))
sum--;
}
cout<<sum%mod<<endl;
continue;
}
f(i,r)
{
if(a[(i+1)%n] == 1)
{
if(i == r-2)
{
if(a[i%n]%2)
sum += a[i%n];
else
sum += (a[i%n]+1);
}
else
{
if(a[i%n]%2)
sum += a[i%n];
else
sum += (a[i%n]-1);}
i++;
continue;
}
sum += a[i%n];
if(i != r-1 && a[i%n]%2 == 1 && i%n < n-1)
sum--;
if(i != r-1 && i%n == n-1 && a[i%n]%2 == 0)
sum--;
}
cout<<sum%mod<<endl;
}
}
return 0;
}
What is wrong with my code . This code is of only 15 points , I am seriously frustrated with this question.
Your code was too fast to solve the subtask!.
1 Like
Thanks 
@utkarsh911 Please look at this to help me. I do not want to waste my hard work to solve this problem.
There are multiple missing cases in your code, even the ones mentioned in the editorial. I’ll suggest you to read the editorial once and figure it out yourself
just annoying , only increased my wrong submissions !
Please Help me with TLE, I don’t know why I am getting TLE my time complexity is O(N+Q)
https://www.codechef.com/viewsolution/39666189
Use fast IO and declare long long mod as const long long mod.
2 Likes
will that make a significant change ?
what is fast IO
4 5 1 7 3
for r = 3 ,
ans = 4 + 5 = 9
Your o/p = 10
1 Like
will that make a significant change ?
what is fast IO ?
It will, yes.
“Fast IO”. (Also, please google it)
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long int t;
const long long mod = 1000000007;
cin >>t;
while(t--) {
long long int n, q, r, sum, turns, extra, ans, oneat;
oneat = 0;
sum = 0;
cin >>n;
long long int a[n], b[n];
for (int i=1; i<n; i++) {
cin >>a[i];
sum += a[i]-a[i]%2;
sum = sum%mod;
b[i] = sum;
if (a[i]==1)
oneat = i;
}
cin >>a[0];
sum += a[0] - 1 + a[0]%2;
sum = sum%mod;
cin >>q;
if (oneat == 0) {
for (int i=0; i<q; i++) {
ans = 0;
cin >>r;
turns = r/n;
extra = r%n;
ans = (turns*sum)%mod;
if (extra-1 > 0)
ans += b[extra-1];
if (extra != 0)
ans += a[extra];
if (r%n==0 && a[r%n]%2==0)
ans += 1;
ans = ans%mod;
cout <<ans <<endl;
}
}
else if (oneat == 1) {
for (int i=0; i<q; i++) {
ans = 0;
cin >>r;
turns = r/n;
extra = r%n;
if (extra > 1)
ans += 1;
ans += turns;
if (turns==0 && extra==1)
ans += 1;
ans = ans%mod;
cout <<ans <<endl;
}
}
else {
for (int i=0; i<q; i++) {
ans = 0;
cin >>r;
turns = r/n;
extra = r%n;
ans = (sum*turns)%mod;
if (a[oneat-1]%2 == 0)
ans -= turns;
else
ans += turns;
if (extra-1 > 0)
ans += b[extra-1];
if (extra != 0)
ans += a[extra];
if (extra > oneat) {
if (a[oneat-1]%2 == 1)
ans += 1;
else
ans -= 1;
}
if (r%n==0 && a[r%n]%2==0)
ans += 1;
ans = ans%mod;
cout <<ans <<endl;
}
}
}
return 0;
}
This should get rid of the TLE.
1 Like
Thanks Let me try, lets see
Thank You Very Much 
I was stuck on this question from 6 days !!!
but I am still taking 0.9 seconds ? shouldn’t it be 0.3-0.5 sec at most
It depends. You can also use \n in place of endl for printing newline
2 Likes
Yes, use \n instead of endl. endl is slower because it forces a flush, which actually unnecessary.
2 Likes
Yes now it is taking only 0.1 sec Thanks