optimized this code

[jLCX216C]

#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;

while(t--){
int flag=0;
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i]; // entering the elements into the array.
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]!=a[j] && a[a[i]] == a[a[j]]){
flag=1;
break;
}
}
}
if(flag!=1){
cout<<"No "<<endl;
}
else{
cout<<"Yes "<<endl;
}
flag=0;
}
return 0;
}

[Repeater]

int a[n+1];
This is illegal (i.e. not C++ code) and dangerous.

What is this program meant to do?

[jLCX216C]

That not the problem I can also take it as a[10000]
main problem in the complexity of this code
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]!=a[j] && a[a[i]] == a[a[j]]){
flag=1;
break;
}
}
}
please help in optimizing this

[Repeater]

What are you trying to do? What is the requirement on this code? What about the numbers that the user enters are you looking for?

[jLCX216C]

I am trying to compare whether in a given array I can found this sequence or not
A1,A2,…,AN. we need to determine if it is possible to choose two indices i and j such that Ai≠Aj, but Asub(Ai) = Asub(Aj).
sub==subscript

[Repeater]

So for this sequence: { 2 , 3, 7, 7 }

the answer would be "true", because A[2] = 7 and A[3] = 7?

[jLCX216C]

No Let me give you the example
for this sequence
1 1 2 3
it is true because Asub(A3)=Asub(A1) and A3≠A1
and for this the answer is no
2 1 3 3
because Asub(A3)=Asub(A4) but A3=A4,
I am starting from 1 index in all the example

[tpb]

The only "optimization" I can see of your brute-force method is to terminate the outer loop when flag becomes true:

for (int i = 1; i <= n && !flag; i++) {

I'll think about other possibilities, though.

[jLCX216C]

@tpb what are those possibilities would you please elaborate

[tpb]

I couldn't think of anything.
Did you try adding the flag test to the outer loop?
Is that not good enough?
If you're trying to solve a programming problem, it's best to give a link to it so I can see the details.

[9LzTpfjN]

Can anybody help me getting 100 in this problem.

Chef has a sequence A1,A2,…,AN; each element of this sequence is either 0 or 1. Appy gave him a string S with length Q describing a sequence of queries. There are two types of queries:

'!': right-shift the sequence A, i.e. replace A by another sequence B1,B2,…,BN satisfying Bi+1=Ai for each valid i and B1=AN
'?': find the length of the longest contiguous subsequence of A with length ≤K such that each element of this subsequence is equal to 1
Answer all queries of the second type.

Input
The first line of the input contains three space-separated integers N, Q and K.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains a string with length Q describing queries. Each character of this string is either '?', denoting a query of the second type, or '!', denoting a query of the first type.


Output
For each query of the second type, print a single line containing one integer — the length of the longest required subsequence.

Constraints
1≤K≤N≤105
1≤Q≤3⋅105
0≤Ai≤1 for each valid i
S contains only characters '?' and '!'

Subtasks
Subtask #1 (30 points):

1≤N≤103
1≤Q≤3⋅103
Subtask #2 (70 points): original constraints

Example Input
5 5 3
1 1 0 1 1
?!?!?
Example Output
2
3
3


Explanation
In the first query, there are two longest contiguous subsequences containing only 1-s: A1,A2 and A4,A5. Each has length 2.
After the second query, the sequence A is [1,1,1,0,1].
In the third query, the longest contiguous subsequence containing only 1-s is A1,A2,A3.
After the fourth query, A=[1,1,1,1,0].
In the fifth query, the longest contiguous subsequence containing only 1-s is A1,A2,A3,A4 with length 4. However, we only want subsequences with lengths ≤K. One of the longest such subsequences is A2,A3,A4, with length 3.


I have got 30 pts.plz help me getting 100.

[jLCX216C]

@yoyohoney what concept are you using for this I have got 100 pts I could optimize your code
Or can you just share the code I will optimize that code itself

[9LzTpfjN]

i m using segment tree but i don't know how to update the binary string.
maybe u can share ur code or help on how to update segment tree.

[jLCX216C]

I think segment tree is not needed here that why I am telling you to share code that will help me in solving your problem

[9LzTpfjN]

I m using brute force so no way my code with which i got 30 pts can fetch me 100 pts.
Can u plz tell me method that u used to solve the problem?

I don't know how to update the binary string .plz explain.what should i write in else condtion?

this is segment tree method

#include <bits/stdc++.h>
#define mp make_pair
#define pii pair<int, int>
#define MA 10000001

using namespace std;

struct node{
int val;
pii left, right;

node(){
val= 0;
left.first = left.second = MA;
right.first = right.second = -1;
}

void merge(const node& n1, const node& n2, int l, int r){
val = max(n1.val, n2.val);
left = n1.left;
right = n2.right;

int l1 = n1.right.first, l2 = n1.right.second, r1 = n2.left.first, r2 = n2.left.second;
if(l1 != -1 && r1 != MA){
int t1 = l1, t2 = r2;
val = max(val, t2 - t1 + 1);
if(t1 == l) left = mp(t1, t2);
if(t2 == r) right = mp(t1, t2);
}
}
};

node seg[300001];

int val[100001] = {0}, n;

void build(int l, int r, int i){
if(l == r){
if(!val[l]) return;
seg[i].val = 1;
pii p = mp(l, r);
seg[i].left = seg[i].right = p;
return;
}
int mid = (l+r)/2;
build(l, mid, i*2+1);
build(mid+1, r, i*2+2);
seg[i].merge(seg[i*2+1], seg[i*2+2], l, r);
}

void update(int l, int r, int i, int pos){
if(l == r){
seg[i].val = 1;
pii p = mp(l, r);
seg[i].left = seg[i].right = p;
return;
}
int mid = (l+r)/2;
if(mid >= pos) update(l, mid, i*2+1, pos);
else update(mid+1, r, i*2+2, pos);
seg[i].merge(seg[i*2+1], seg[i*2+2], l, r);
}

void print(){
for(int j = 0; j < 9; j++)
cout << j << " --> " << seg[j].val << " (" << seg[j].left.first << " " << seg[j].left.second << ") , (" << seg[j].right.first << " " << seg[j].right.second << ") " << endl;
}

int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);

int q,k;
cin >> n >> q>>k;
char s[n];
for(i=0;i<n;i++)
{
cin>>a[i];
s[i]=a[i]+'0';
}
for(int j = 0; j < n; j++)
if(s[j] == '0') val[j] = 0;
else val[j] = 1;

build(0, n-1, 0);
while(q--){
char type;
cin >> type;
if(type == '?') cout << seg[0].val << endl;
else{
}
}
return 0;
}

[jLCX216C]

@yoyohoney I have got 100 by using brute force itself ,It is not a completely a brute force but still its work for all cases
I cann't share the same ans as judge would banned both account so give me your brute force method I would optimize it with some specific conditions

[9LzTpfjN]

u can send me ur code.I myself will optimize my code by looking through which i can get to know my mistake

[jLCX216C]

I am using bitmasking this is not the complete code but you will get the idea
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
int main()
{
int n,q,k,count;
string str;
cin>>n>>q>>k;
bitset<MAX>s,c;
//inserting bits in array
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
s[i]=temp;
}
cin>>str;
for(int i=0;i<q;i++)
{
//making duplicate bitset
c=s;
if(str[i]=='?')
{
count=0;
while(c!=0)
{
//using bitmask to count maximum no of continuous 1's-O(1's bit)
c=(c&(c<<1));
count++;
}
if(count>k)
cout<<k<<"\n";
else
cout<<count<<"\n";
}
else
{
//shifting each bit to right and updating first bit with previous last bit
bool lb=s[n-1];
s=s>>1;
s[n-1]=lb;
}
}
return 0;
}
If you share your brute force code then it would be good as I would love to do by that method also
So please do share that as well I am willing to do that also

[9LzTpfjN]

getting tle using your method

[9LzTpfjN]

Has anybody got 100 in hmappy1?
Can you plz share ur approach.