oj.uz

Submission #131851

# Submission time Handle Problem Language Result Execution time Memory
131851 2019-07-17T19:47:58 Z hamzqq9 Naan (JOI19_naan) C++14
29 / 100
 179 ms 14160 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 10000000000000
#define N 2019
#define MOD 998244353
using namespace std;
 
#define greater bos
 
struct frac {
 
	ll u,d;
 
};
 
frac mul(frac a,frac b) {
 
	ll u=(ll)a.u*b.u;
	ll d=(ll)a.d*b.d;
 
	ll g=__gcd(abs(u),abs(d));
 
	return {u/g,d/g};
 
}
 
frac dvd(frac a,frac b) {
 
	swap(b.u,b.d);
 
	return mul(a,b);
 
}
 
frac sub(frac a,frac b) {
 
	ll u=(ll)a.u*b.d-(ll)b.u*a.d;
	ll d=(ll)a.d*b.d;
 
	ll g=__gcd(abs(u),abs(d));
 
	return {u/g,d/g};
 
}
 
frac add(frac a,frac b) {
 
	ll u=(ll)a.u*b.d+(ll)b.u*a.d;
	ll d=(ll)a.d*b.d;
 
	ll g=__gcd(abs(u),abs(d));
 
	return {u/g,d/g};
 
}
 
bool eq(frac a,frac b) {
 
	return (ll)a.u*b.d==(ll)b.u*a.d;
 
}
 
bool greateq(frac a,frac b) {
	
	return a.u/a.d>=b.u/b.d;
 
}
 
bool greater(frac a,frac b) {

	return a.u/a.d>b.u/b.d;
 
}
 
frac gmin(frac a,frac b) {
 
	return greater(a,b)?b:a;	
 
}
 
int gnext(frac a) {
 
	return a.u/a.d+1;
 
}

frac app(frac a) {

	ll g=__gcd(a.u,a.d);

	return {a.u/g,a.d/g};

}
 
int n,l;
int v[N][N],pre[N][N],u[N],ptr[N];
frac req[N];
vector<frac> cp[N];
 
int main() {
 
	scanf("%d %d",&n,&l);
 
	for(int i=1;i<=n;i++) {
 
		req[i]={0,n};
 
		for(int j=1;j<=l;j++) {
 
			scanf("%d",&v[i][j]);

			pre[i][j]=pre[i][j-1]+v[i][j];
 
			req[i].u+=v[i][j];
 
		}
 
	}	
 
	for(int i=1;i<=n;i++) {
 
		cp[i].pb({0,1});

		for(int j=1;j<=n;j++) {

			int bas=1,son=l;

			while(bas<=son) {

				if((ll)pre[i][orta]*n<(ll)req[i].u*j) bas=orta+1;
				else son=orta-1;

			}

			// w==(j*sum-n*pre[i][son]+son*v[i][bas]*n)/v[i][bas]*n

			cp[i].pb(app({(ll)j*pre[i][l]-(ll)n*pre[i][son]+(ll)son*v[i][bas]*n,(ll)v[i][bas]*n}));

		}	
 
	}
 
	vector<frac> res;
	vector<int> ans;
 
	for(int i=1;i<=n;i++) {
 
		frac mn={inf,1};
		int tut=-1;
 
		for(int j=1;j<=n;j++) {
 
			if(u[j]) continue ;
 
			while(sz(res) && ptr[j]<n && greater(res.back(),cp[j][ptr[j]])) {
 
				++ptr[j];
 
			}
 
			if(ptr[j]<n) {
 
				if(greater(mn,cp[j][ptr[j]+1])) {
 
 					mn=cp[j][ptr[j]+1];
					tut=j;
 
				}
 
			}
 
		}
 
		ans.pb(tut);
		u[tut]=1;
 
		res.pb(mn);
 
	}
 
	res.ppb();
 
	for(auto x:res) printf("%lld %lld\n",x.u,x.d);
 
	for(auto x:ans) printf("%d ",x);
 
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:110: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:118:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&v[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 3 ms 504 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 3 ms 504 KB Output is correct
31 Correct 3 ms 476 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 3 ms 504 KB Output is correct
35 Correct 3 ms 504 KB Output is correct
36 Correct 3 ms 504 KB Output is correct
37 Correct 3 ms 504 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 3 ms 504 KB Output is correct
40 Correct 3 ms 376 KB Output is correct
41 Correct 2 ms 352 KB Output is correct
42 Correct 3 ms 504 KB Output is correct
43 Incorrect 179 ms 14160 KB X_i is not increasing
44 Halted 0 ms 0 KB -