Submission #152265

#TimeUsernameProblemLanguageResultExecution timeMemory
152265usernameNaan (JOI19_naan)C++14
29 / 100
673 ms32128 KiB
#pragma GCC optimize("O3") #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 f first #define s second #define endl '\n' #define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false) const int maxn=2009; int n,l,p[maxn],v[maxn][maxn]; bitset<maxn>us; 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,1,n){ int opt=-1; pii ls={1,0}; 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}; if(v[j][k]*n<0||v[j][k]*n>4e11)return 0; assert(cur.s<2e8&&cur.s>=0); // assert(v[j][k]*n*cur.s>=0); while((__int128)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((__int128)t.f*ls.s<(__int128)ls.f*t.s)opt=j,ls=t; } p[i]=opt; us[opt]=1; cur=ls; cout<<ls.f<<" "<<ls.s<<endl; } REP(i,1,n)cout<<p[i]+1<<" "; REP(i,0,n)if(!us[i])cout<<i+1<<endl; }

Compilation message (stderr)

naan.cpp:16: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...