11100 - OJ accepts incorrect solutions

[avlahov]

OJ gave me AC although I sent incorrect code! It seems to only check the correctness of k (the minimum number of pieces), but does not care much for the format of the k sequences. Here's the code that got AC:

Code: Select all

#include <iostream>

using namespace std;

int a[10000];
int b[10000];
int last = 9999;

int L[10000];
int R[10000];

int infinity = 1000001;

void merge(int p, int q, int r) {

		int n1 = q - p + 1;
		int n2 = r - q;

		for(int i=1; i<=n1; i++)
			L[i] = a[p + i -1];

		for(int j=1; j<=n2; j++)
			R[j] = a[q + j];

		L[n1+1] = infinity;
		R[n2+1] = infinity;

		int l_i = 1;
		int r_j = 1;

		for(int k = p; k<= r; k++) {

			if(L[l_i] <= R[r_j]) {
				a[k] = L[l_i];
				l_i++;
			} else {
				a[k] = R[r_j];
				r_j++;
			}
		}
}

void msort(int p, int r) {
	
	if(p < r) {
		int q = (p+r)/2;

		msort(p, q);
		msort((q+1), r);
		merge(p, q, r);
	}
}

int find_big(int n) {

	int res = -1;

	for(int i=(n-1); i>=0; i--) {
		if(b[i]>0) {
			res = i;
			break;
		}
	}

	return res;
}

void main() {

	int n;

	int no_line = 1;

	while(cin>>n) {
		
		if(n == 0)
			break;

		if(no_line != 1)
			cout<<endl;

		no_line = 2;

		for(int i=0; i<n; i++)
			cin>>a[i];

		msort(0, (n-1));

		for(int i=0; i<n; i++)
			b[i] = a[i];
		
		int stat = find_big(n);
		int pass = 0;
		int max;

		while(stat >= 0) {
			
			max = b[stat];
			b[stat] = -1;
			
			for(int i=(stat-1); i>=0; i--) {

				if((b[i] > 0) && (b[i] < max)) {
					max = b[i];
					b[i] = -1;
				}
			}

			pass++;
			stat = find_big(n);
		}
		
		cout<<pass<<endl;
		
		//this should not be accepted!!!
		for(int i=0; i<n; i++)
			cout<<a[i]<<endl;
	}
}

[chunyi81]

Did you notice the yellow tick before the problem? This means that there can be more than one possible correct minimum sequence.

Now please remove your ACed code as it is a spoiler.

[avlahov]

I am aware that there can be more than one correct minimum sequence. However, my code is not even trying to find correct sequences. It just outputs the correct k, followed by the sorted input with each bag dimension on a separate line. This is obviously wrong, yet it gets AC...

[yiuyuho]

Probably because the judge input is not strong enough, it happens A LOT as you do more problems. They improve the data and rejudge over time though, so don't worry too much about it.

[Carlos]

under investigation