oj.uz

Submission #97707

# Submission time Handle Problem Language Result Execution time Memory
97707 2019-02-17T18:37:26 Z KLPP Permutation Recovery (info1cup17_permutation) C++14
43 / 100
 1365 ms 683008 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define sz 211
struct longInt{
	int arr[sz];
};
longInt *sum(longInt *a, longInt*b){
	longInt *ans=new longInt();
	//for(int i=0;i<sz;i++)ans->arr[i]=0;
	int carry=0;
	for(int i=0;i<sz;i++){
		ans->arr[i]=(a->arr[i]+b->arr[i]+carry)%10;
		if(a->arr[i]+b->arr[i]+carry>=10)carry=1;
		else carry=0;
	}
	return ans;
}
longInt *dif(longInt *a, longInt*b){//compute a-b
	longInt *ans=new longInt();
	//for(int i=0;i<sz;i++)ans->arr[i]=0;
	int carry=0;
	for(int i=0;i<sz;i++){//cout<<a->arr[i]<<" "<<b->arr[i]<<" "<<carry<<endl;
		ans->arr[i]=(a->arr[i]-b->arr[i]+carry)%10;
		//cout<<ans->arr[i]<<endl;
		if(a->arr[i]-b->arr[i]+carry<0){
			ans->arr[i]+=10;carry=-1;
			ans->arr[i]%=10;
		}else carry=0;
		//cout<<ans->arr[i]<<endl;
	}
	return ans;
}
bool Bigger(longInt *a, longInt*b){//compute a-b
	for(int i=sz-1;i>-1;i--){
		if(a->arr[i]>b->arr[i])return true;
		if(a->arr[i]<b->arr[i])return false;
	}
	return true;
}
void print(longInt *l){
	bool zeros=true;
	for(int i=9;i>-1;i--){
		if(l->arr[i]==0 && !zeros)cout<<l->arr[i];
		if(l->arr[i]!=0){
			cout<<l->arr[i];
			zeros=false;
		}
	}
	cout<<endl;
}
int main(){
	longInt *ONE=new longInt();
	for(int i=1;i<sz;i++)ONE->arr[i]=0;
	ONE->arr[0]=1;
	int n;
	cin>>n;
	longInt *L[n];
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		L[i]=new longInt();
		for(int j=0;j<sz;j++){//cout<<j<<" "<<s.size()-j-1<<endl;
			if(s.size()>=j+1)L[i]->arr[j]=s.at(s.size()-j-1)-'0';
			else L[i]->arr[j]=0;
		}
		//print(L[i]);
	}

	longInt *diff[n];
	diff[0]=L[0];
	for(int i=1;i<n;i++)diff[i]=dif(L[i],L[i-1]);
	//print(diff[31]);
	/*for(int i=0;i<n;i++){
		print(diff[i]);
	}*/
	int per[n];
	for(int i=0;i<n;i++)per[i]=1;
	for(int i=1;i<n;i++){
		longInt *x=diff[i];
		x=dif(x,ONE);
		for(int j=i-1;j>-1;j--){
			if(Bigger(x,diff[j])){
				x=dif(x,diff[j]);
				per[i]++;
			}else per[j]++;
		}
	}
	for(int i=0;i<n;i++)cout<<per[i]<<" ";
	cout<<endl;	
	return 0;
}

Compilation message

permutation.cpp: In function 'int main()':
permutation.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(s.size()>=j+1)L[i]->arr[j]=s.at(s.size()-j-1)-'0';
       ~~~~~~~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct
3 Correct 264 ms 153328 KB Output is correct
4 Correct 426 ms 206032 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct
3 Correct 264 ms 153328 KB Output is correct
4 Correct 426 ms 206032 KB Output is correct
5 Runtime error 1365 ms 683008 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct
3 Correct 264 ms 153328 KB Output is correct
4 Correct 426 ms 206032 KB Output is correct
5 Runtime error 1365 ms 683008 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct
3 Correct 264 ms 153328 KB Output is correct
4 Correct 426 ms 206032 KB Output is correct
5 Runtime error 1365 ms 683008 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct
3 Correct 264 ms 153328 KB Output is correct
4 Correct 426 ms 206032 KB Output is correct
5 Runtime error 1365 ms 683008 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 61 ms 35168 KB Output is correct
3 Correct 264 ms 153328 KB Output is correct
4 Correct 426 ms 206032 KB Output is correct
5 Runtime error 1365 ms 683008 KB Execution killed with signal 9 (could be triggered by violating memory limits)