Help me find a bug for solving the problem Moamen and k-subarrays in Codeforces Round #737 (Div. 2)

Revision en1, by 018429, 2021-08-25 09:33:17

About the problem 1557B,what's the matter with following code , I can't figure out why it is always failed in case 58 of third test,I am almost crushed @^-^@

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin >> n >> k;
		vector<int> a(n),b(n);
		for(int i = 0;i < n;i++){
			cin >> a[i];
			b[i] = a[i]; 
		}
		sort(b.begin(),b.end());
		map<int,int> nxt;
		for(int i = 0;i < n - 1;i++)nxt[b[i]] = b[i+1];
		//nxt[b[n-1]] = b[n-1];
		int seg = 1;
		for(int i = 1;i < n;i++)if(a[i] != nxt[a[i-1]])seg++;
		if(seg <= k){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
  	return 0;
}

OK,I just rewrite the code again,and made a mistake again,I loop from i to n — 1 to make nxt[b[i] = b[i+1],I find I even pass 10 test,than I realize the last number's next value I didn't define,make the default value zero in map,in the case n = 4,k = 1,array like 3 0 1 2,we can easily hack the code of mine,Finally,the problem is solved,so happy^^

Tags #help me, #debug

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English 018429 2021-08-25 09:42:31 2 Tiny change: 'en pass 10 test,then' -> 'en pass 10th test,then'
en2 English 018429 2021-08-25 09:41:04 208
en1 English 018429 2021-08-25 09:33:17 1199 Initial revision (published)