Submission #120296

#	Time	Username	Problem	Language	Result	Execution time	Memory
120296		errorgorn	Naan (JOI19_naan)	C++14	29 / 100	39 ms	3644 KiB

naan

#include <bits/stdc++.h>
using namespace std;
int n,l;
int arr[2005][2005];
int perm[2005];
vector<int> rem;
struct fraction{
	long long a,b;
	fraction (){
		init();
	}
	fraction(long _a,long long _b){
		long long c=gcd(_a,_b);
		a=_a/c;
		b=_b/c;
	}
	fraction (fraction* i){
		a=i->a;
		b=i->b;
	}
	long long gcd(long long i,long long j){
		if (i<j) swap(i,j);
		while (j!=0){
			i%=j;
			swap(i,j);
		}
		return i;
	}
	void add_int(long long i){
		a+=b*i;
	}
	void add(fraction* i){
		a*=i->b;
		a+=i->a*b;
		b*=i->b;
		long long c=gcd(a,b);
		a/=c;
		b/=c;
	}
	void minus(fraction* i){
		a*=i->b;
		a-=i->a*b;
		b*=i->b;
		long long c=gcd(a,b);
		a/=c;
		b/=c;
	}
	void multiply(fraction *i){
		a*=i->a;
		b*=i->b;
		long long c=gcd(a,b);
		a/=c;
		b/=c;
	}
	void divide(fraction *i){
		a*=i->b;
		b*=i->a;
		long long c=gcd(a,b);
		a/=c;
		b/=c;
	}
	void divide(long long i){
		b*=i;
		long long c=gcd(a,i);
		a/=c;
		b/=c;
	}
	long long  whole(){
		return a/b;
	}
	long long frac(){
		return a%b;
	}
	void remaining(fraction* i){
		if (i->a%i->b==0){
			init();
		}
		else{
			b=i->b;
			a=b-i->frac();
		}
	}
	void init_inf(){
	    a=1;
	    b=0;
	}
	void init(){
		a=0;
		b=1;
	}
	void init (fraction* i){
		a=i->a;
		b=i->b;
	}
	void init (fraction* i,long long j){
		a=i->a*j;
		b=i->b;
		long long c=gcd(b,j);
		a/=c;
		b/=c;
	}
	void assign(fraction *i){
		a=i->a;
		b=i->b;
	}
	bool cmp (fraction *j){
		return a*j->b<j->a*b;
	}
};
fraction *total[2005];
fraction *ans[2005];
int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&l);
	int t;
	for (int x=0;x<n;x++){
		t=0;
		for (int y=0;y<l;y++){
			scanf("%d",&arr[x][y]);
			t+=arr[x][y];
		}
		rem.push_back(x);
		total[x]=new fraction(t,n);
	}
	fraction *curr=new fraction();
	fraction *best=new fraction();
	fraction *val=new fraction();
	fraction *len=new fraction();
	fraction *remainder=new fraction();
	int index;
	int curr_index;
	int pointer;
	int X=0;
	int best_index;
	while (!rem.empty()){
		remainder->remaining(curr);
		best->init_inf();
		curr_index=0;
		for (int x=0;x<rem.size();x++){
			index=rem[x];
			val->init(remainder,arr[index][curr->whole()]);
			len->init(remainder);
			if (total[index]->cmp(val)){
				len->divide(val);
				len->multiply(total[index]);
			}
			else{
				pointer=curr->whole();
				if (curr->frac()!=0) pointer++;
				while (val->cmp(total[index])){
					if (pointer==l){
						printf("%d-%d\n",n,l);
						return 0;
					}
					val->add_int(arr[index][pointer]);
					pointer++;
					len->add_int(1);
				}
				//printf("before:\n%lld %lld\n%lld %lld\n",len->a,len->b,val->a,val->b);
				val->minus(total[index]); //val is now extra
				val->divide(arr[index][--pointer]);
				len->minus(val);
				//printf("after:\n%lld %lld\n%lld %lld\n",len->a,len->b,val->a,val->b);
			}
			if (len->cmp(best)){
				best->assign(len);
				best_index=curr_index;
			}
			curr_index++;
		}
		//printf("%lld %lld\n",best->a,best->b);
		//printf("%d %d\n",index,best_index);
		curr->add(best);
		ans[X]=new fraction(curr);
		perm[X]=rem[best_index];
		//printf("eraseing %d at index %d\n",rem[best_index],best_index);
		rem.erase(rem.begin()+best_index);
		X++;
	}
	for (int x=0;x<n-1;x++){
		printf("%lld %lld\n",ans[x]->a,ans[x]->b);
	}
	for (int x=0;x<n;x++){
		printf("%d ",perm[x]+1);
	}
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:139:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<rem.size();x++){
                ~^~~~~~~~~~~
naan.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&l);
  ~~~~~^~~~~~~~~~~~~~
naan.cpp:119:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&arr[x][y]);
    ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:175:25: warning: 'best_index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   perm[X]=rem[best_index];
                         ^

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71