oj.uz

답안 #254007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254007 2020-07-29T09:05:04 Z TadijaSebez Naan (JOI19_naan) C++11
29 / 100
 1892 ms 55936 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005;
struct frac{
	ll p,q;
	frac(){}
	frac(ll a,ll b=1){if(b<0)a=-a,b=-b;ll g=__gcd(abs(a),b);a/=g;b/=g;p=a;q=b;}
	frac operator * (ll b) const {return frac(p*b,q);}
	frac operator - (frac b) const {return frac(p*b.q-b.p*q,q*b.q);}
	frac operator + (frac b) const {return frac(p*b.q+b.p*q,q*b.q);}
	frac operator * (frac b) const {return frac(p*b.p,q*b.q);}
	frac operator / (frac b) const {return frac(p*b.q,q*b.p);}
	bool operator < (frac b) const {return p*b.q<b.p*q;}
	void print(){printf("(%lld/%lld)",p,q);}
}p[N][N];
frac operator -= (frac&a,frac b){a=a-b;}
int v[N][N],sum[N],ans[N];
bool was[N];
int main(){
	int n,l;
	scanf("%i %i",&n,&l);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=l;j++){
			scanf("%i",&v[i][j]);
			sum[i]+=v[i][j];
		}
		frac mul(1);
		for(int j=1,ptr=1;j<=n;j++){
			frac need=frac(sum[i],n);
			while(mul*v[i][ptr]<need){
				need-=mul*v[i][ptr];
				mul=frac(1);
				ptr++;
			}
			frac val=mul*v[i][ptr];
			frac tmp=need/val;
			mul=mul-(mul*tmp);
			p[i][j]=frac(ptr-1)+(frac(1)-mul);
		}
	}
	for(int i=1;i<=n;i++){
		frac mn=frac(l+1);
		int k;
		for(int j=1;j<=n;j++)if(!was[j]){
			if(p[j][i]<mn){
				mn=p[j][i];
				k=j;
			}
		}
		if(i!=n)printf("%lld %lld\n",mn.p,mn.q);
		ans[i]=k;
		was[k]=1;
	}
	for(int i=1;i<=n;i++)printf("%i ",ans[i]);
	return 0;
}

Compilation message

naan.cpp: In function 'frac operator-=(frac&, frac)':
naan.cpp:17:40: warning: no return statement in function returning non-void [-Wreturn-type]
 frac operator -= (frac&a,frac b){a=a-b;}
                                        ^
naan.cpp: In function 'int main()':
naan.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
naan.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i",&v[i][j]);
    ~~~~~^~~~~~~~~~~~~~~
naan.cpp:52:9: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ans[i]=k;
   ~~~~~~^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 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 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 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 512 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 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 0 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 512 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 0 ms 384 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 2 ms 384 KB Output is correct
43 Correct 308 ms 12412 KB Output is correct
44 Incorrect 1892 ms 55936 KB X_i is not increasing
45 Halted 0 ms 0 KB -