oj.uz

Submission #119256

# Submission time Handle Problem Language Result Execution time Memory
119256 2019-06-20T18:53:06 Z KLPP Naan (JOI19_naan) C++14
29 / 100
 4000 ms 3892 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)

lld GCD(lld x, lld y){
  if(y==0)return x;
  return GCD(y,x%y);
}
struct frac{
  lld n,d;
};
frac add(frac a, frac b){
  frac ans;
  ans.n=a.n*b.d+a.d*b.n;
  ans.d=a.d*b.d;
  lld g=GCD(ans.n,ans.d);
  ans.n/=g;
  ans.d/=g;
  return ans;
}
frac mult(frac a,lld b){
  frac ans;
  ans.n=a.n;
  ans.d=a.d;
  ans.n*=b;
  lld g=GCD(ans.n,ans.d);
  ans.n/=g;
  ans.d/=g;
  return ans;
}
frac sub(frac a, frac b){
  frac ans;
  ans.n=a.n*b.d-a.d*b.n;
  ans.d=a.d*b.d;
  lld g=GCD(ans.n,ans.d);
  ans.n/=g;
  ans.d/=g;
  return ans;
}
bool leq(frac a, frac b){
  if(a.n*b.d<=a.d*b.n)return true;
  return false;
}
bool leq(frac a, lld b){
  if(a.n<=a.d*b)return true;
  return false;
}
frac reduce(frac a){
  lld g=GCD(a.n,a.d);
  frac ans;
  ans.n=a.n/g;
  ans.d=a.d/g;
  return ans;
}
void print(frac a){
  cout<<a.n<<" "<<a.d<<" ";
}
int main(){
  int n,l;
  cin>>n>>l;
  lld grid[n][l];
  lld sum[n];
  rep(i,0,n){
    sum[i]=0;
    rep(j,0,l){
      cin>>grid[i][j];
      sum[i]+=grid[i][j];
    }
  }
  int per[n];
  rep(i,0,n)per[i]=i;
  do{
    frac point;
    point.n=0;
    point.d=1;
    bool B=true;
    vector<pair<lld,lld> > v;
    rep(i,0,n){
      frac s;
      s.n=sum[per[i]];
      s.d=n;
      frac f;
      f.n=s.n;
      f.d=grid[per[i]][point.n/point.d]*s.d;
      f=reduce(f);
      //print(point);
      //cout<<endl;
      while(!leq(add(f,point),point.n/point.d+1) && point.n<point.d*(l-1)){
	//print(point);print(f);print(s);cout<<endl;
	
	frac u;
	u.n=point.n/point.d+1;
	u.d=1;
	u=sub(u,point);
	s=sub(s,mult(u,grid[per[i]][point.n/point.d]));
	point.n=point.n/point.d+1;
	point.d=1;
	f.n=s.n;
	f.d=grid[per[i]][point.n/point.d]*s.d;
	f=reduce(f);
	//print(point);print(f);print(s);cout<<endl;
      }
      if(!leq(add(f,point),point.n/point.d+1) && point.n>=point.d*(l-1)){
	B=false;
	i=n;
      }
      point=add(f,point);
      /*frac PB;
      PB.n=point.n;
      PB.d=point.d;
      v.push_back(PB);*/
      v.push_back(pair<lld,lld>(point.n,point.d));
      //print(point);cout<<endl;
    }
    //cout<<B<<endl;
    if(B){
      rep(i,0,v.size()-1)cout<<v[i].first<<" "<<v[i].second<<endl;
      rep(i,0,n)cout<<per[i]+1<<" ";
      cout<<endl;
      return 0;
    }
  }while(next_permutation(per,per+n));
  cout<<-1<<endl;
  return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:5:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
naan.cpp:119:11:
       rep(i,0,v.size()-1)cout<<v[i].first<<" "<<v[i].second<<endl;
           ~~~~~~~~~~~~~~         
naan.cpp:119:7: note: in expansion of macro 'rep'
       rep(i,0,v.size()-1)cout<<v[i].first<<" "<<v[i].second<<endl;
       ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 428 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 428 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 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 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 3 ms 356 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 12 ms 380 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 512 KB Output is correct
34 Correct 4 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 2 ms 384 KB Output is correct
39 Correct 4 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 4 ms 384 KB Output is correct
43 Execution timed out 4030 ms 3892 KB Time limit exceeded
44 Halted 0 ms 0 KB -