PROBLEM LINK:
Author: Akshat Gupta
Tester: Anshu Garg
Editorialist: Akshat Gupta
DIFFICULTY:
CAKEWALK
PROBLEM:
Given an Array A of length N and an integer X.
we need to find the farthest index such A_i < X
EXPLANATION:
In the Problem it is given that if we destroy the i^{th} house all the bases before it get destroyed.
So we need to find maximum i such that A_i < X
For this we can simply iterate over the array and find the largest i which satisfies the given condition.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,x;cin>>n>>x;
int ans=0;
for(int i=0;i<n;i++){
int a;cin>>a;
if(a<x)ans=i+1;
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2401
#endif
long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l,int r,char end){
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int _runtimeTerror_()
{
int T = readIntLn(1, 100);
int mx_N = 0, mn_N = 1e6, sum_N = 0;
for(int i=1;i<=T;++i) {
int N = readIntSp(1, 1e5), X = readIntLn(1, 1e9);
amax(mx_N, N);
amin(mn_N, N);
sum_N += N;
cerr << N << " " << X << "\n";
vector<int> a(N);
for(int i=0;i<N-1;++i) {
a[i] = readIntSp(1, 1e9);
}
a[N - 1] = readIntLn(1, 1e9);
int ans = 0;
for(int i=N-1;i>=0;--i) {
if(a[i] < X) {
ans = i + 1;
break;
}
}
cout << ans << "\n";
}
cerr << T << "\n";
cerr << mn_N << " " << mx_N << " " << sum_N << "\n";
assert(sum_N <= 1e5);
assert(getchar() == -1);
return 0;
}
// <= X instead of < X
// constraints on sum_N, and mx_N should be 1e5 in one case atleast
int main()
{
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initncr();
#endif
int TESTS = 1;
//cin >> TESTS;
while(TESTS--) {
_runtimeTerror_();
}
return 0;
}