Submission #535252

#	Time	Username	Problem	Language	Result	Execution time	Memory
535252		shayanebrahimi	Naan (JOI19_naan)	C++14	100 / 100	852 ms	130896 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl                        '\n'
#define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll MOD=1e9+7;//998244353//1e9+9;
//ll tavmd(ll a,ll b){if(b==0){return 1;}if(b%2==0){ll x=tavmd(a,b/2);return(x*x)%MOD;}else{return(a%MOD*tavmd(a,b-1)%MOD)%MOD;}}
const ll MAXN=2e3+10;
const ll INF=8e18;
const ll LOG=30;
ll a[MAXN][MAXN],n,k,p[MAXN];
pair<ll,ll>ans[MAXN];
bool chc[MAXN];
int main(){
      fast_io;
      cin>>n>>k;
      for(int i=0;i<n;i++)
            for(int j=0;j<k;j++)
                  cin>>a[i][j];
      vector<pair<ll,pair<ll,ll>>>ls[n-1];
      for(int i=0;i<n;i++){
            ll s=0;
            for(int j=0;j<k;j++)
                  s+=a[i][j];
            ll pt=0,pf=0;
            for(int j=0;j<n-1;j++){
                  while(pt<k&&(pf+a[i][pt])*n<=s*(j+1))
                        pf+=a[i][pt++];
                  ls[j].push_back({i,{s*(j+1)-pf*n+pt*a[i][pt]*n,a[i][pt]*n}});
            }
      }
      for(int i=0;i<n-1;i++)
            sort(ls[i].begin(),ls[i].end(),[](pair<ll,pair<ll,ll>>x,pair<ll,pair<ll,ll>>y){
            if(x.second.first/x.second.second!=y.second.first/y.second.second)
                  return x.second.first/x.second.second<y.second.first/y.second.second;
            return(x.second.first%x.second.second)*y.second.second<x.second.second*(y.second.first%y.second.second);
      });
      for(int i=0;i<n-1;i++){
            for(int j=0;j<n;j++)
                  if(!chc[ls[i][j].first]){
                        chc[ls[i][j].first]=true;
                        p[i]=ls[i][j].first;
                        ans[i]=ls[i][j].second;
                        break;
                  }
      }
      for(int i=0;i<n;i++)
            if(!chc[i])
                  p[n-1]=i;
      for(int i=0;i<n-1;i++)
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
      for(int i=0;i<n;i++)
            cout<<p[i]+1<<" ";
      return 0;
}

Compilation message (stderr)

naan.cpp:5:9: warning: ISO C++11 requires whitespace after the macro name
    5 | #define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      |         ^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71