oj.uz

Submission #120296

# Submission time Handle Problem Language Result Execution time Memory
120296 2019-06-24T06:56:23 Z errorgorn Naan (JOI19_naan) C++14
29 / 100
 39 ms 3644 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 3 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 3 ms 384 KB Output is correct
38 Correct 2 ms 384 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 3 ms 384 KB Output is correct
43 Incorrect 39 ms 3644 KB Expected integer, but "563-467" found
44 Halted 0 ms 0 KB -