Submission #97707

#	Time	Username	Problem	Language	Result	Execution time	Memory
97707		KLPP	Permutation Recovery (info1cup17_permutation)	C++14	43 / 100	1365 ms	683008 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6