Submission #152122

#TimeUsernameProblemLanguageResultExecution timeMemory
152122usernameNaan (JOI19_naan)C++14
29 / 100
156 ms6168 KiB
#pragma GCC optimize("O3") #include<stdint.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<ext/rope> using namespace __gnu_pbds; using namespace __gnu_cxx; #define VIS(it,con) for(auto it=con.begin();it!=con.end();++it) #define pob pop_back #define pf push_front #define pof pop_front #define MIN(x,y) (x=min(x,(y))) #define MAX(x,y) (x=max(x,(y))) #define mid (l+r>>1) #define lch (idx*2+1) #define rch (idx*2+2) /*****************************************************************************/ #include<bits/stdc++.h> #define int int_fast64_t using namespace std; typedef pair<int,int> pii; #define REP(i,j,k) for(register int i=(j);i<(k);++i) #define RREP(i,j,k) for(register int i=int(j)-1;i>=(k);--i) #define ALL(a) a.begin(),a.end() #define pb push_back #define f first #define s second #define endl '\n' #define __debug #ifdef __debug #define IOS (void)0 #define de(...) cerr<<__VA_ARGS__ #define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);} #else #define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false) #define de(...) (void)0 #define ar(...) (void)0 #endif /***********************************default***********************************/ const int maxn=2009; int n,l,p[maxn],v[maxn][maxn]; bitset<maxn>us; bool operator<(pii a,pii b){ int k=a.f/a.s-b.f/b.s; return k?k<0:(a.f%a.s)*b.s<(b.f%b.s)*a.s; } main(){ IOS; cin>>n>>l; REP(i,0,n){ v[i][0]=0; REP(j,0,l)cin>>v[i][j+1],v[i][j+1]+=v[i][j]; } pii cur={0,1}; REP(i,0,n){ int opt=-1; pii ls={l+1,1}; REP(j,0,n){ if(us[j])continue; int k=cur.f/cur.s; pii t={v[j][k]*n*cur.s+(v[j][k+1]-v[j][k])*(cur.f%cur.s)*n+v[j][l]*cur.s,n*cur.s}; while(k<l&&v[j][k+1]*t.s<=t.f)++k; int vv=v[j][k+1]-v[j][k]; t={k*vv*n+__int128(t.f*n+t.s-1)/t.s-v[j][k]*n,vv*n}; if(t<ls)opt=j,ls=t; } p[i]=opt; us[opt]=1; cur=ls; if(i+1<n)cout<<ls.f<<" "<<ls.s<<endl; } REP(i,0,n)cout<<p[i]+1<<" "; }

Compilation message (stderr)

naan.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...