Submission #119256

#	Time	Username	Problem	Language	Result	Execution time	Memory
119256		KLPP	Naan (JOI19_naan)	C++14	29 / 100	4030 ms	3892 KiB

naan

#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 (stderr)

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 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71