oj.uz

Submission #873361

# Submission time Handle Problem Language Result Execution time Memory
873361 2023-11-14T23:24:16 Z ofrankel Naan (JOI19_naan) C++17
29 / 100
 317 ms 46416 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,l;
vector<vector<int>>v;
ll gc(ll a,ll b){
    if(!b)return a;
    return gc(b,a%b);
}
class frac{
public:
    ll a,b;
    frac(ll _a,ll _b):a(_a),b(_b){reduce();}
    frac(ll x):a(x),b(1){}
    void reduce(){if(ll g=gc(a,b)){a/=g;b/=g;}}
    bool operator <(const frac& other){return a*other.b<other.a*b;}
    frac operator +( const frac& other){return frac(a*other.b+b*other.a,b*other.b);}
};
pair<vector<pair<ll,ll>>,vector<int>> solve(int N,int L,vector<vector<int>>V){
    n=N;l=L;v=move(V);
    vector<int>was(n);
    vector<int>p(n);
    vector<pair<ll,ll>>t(n-1);
    vector<ll>s(n);for(int i=0;n>i;++i)for(int j:v[i])s[i]+=j;
    vector<vector<frac>>g(n,vector<frac>(n-1,l));
    for(int i=0;n>i;++i){
        int ind=0;ll kam=0;
        for(int j=0;n>j+1;++j){
		if(v[i][ind]*n>=kam+s[i]){
			g[i][j]=frac((ll)v[i][ind]*n*ind+kam+s[i],v[i][ind]*n);
				kam+=s[i];}
		else{
			int nishar=s[i]+kam-v[i][ind]*n;
				while(nishar>v[i][++ind]*n){nishar-=v[i][ind]*n;}
			kam=nishar;
			g[i][j]=frac((ll)v[i][ind]*n*ind+kam,v[i][ind]*n);}
        }
            
    }
    for(int i=0;n>i+1;++i){frac cur(l);int ind=0;for(int j=0;n>j;++j)if(!was[j]&&g[j][i]<cur){cur=g[j][i];ind=j;}t[i]={cur.a,cur.b};was[ind]=1;p[i]=ind+1;}
    for(int i=0;n>i;++i)if(!was[i])p[n-1]=i+1;
    return {t,p};
}


int main()
{
    std::ios::sync_with_stdio(0);cin.tie(0);
    int N,L;cin>>N>>L;
    vector<vector<int>>V(N,vector<int>(L));
    for(auto&i:V)for(auto&j:i)cin>>j;
    auto [t,p]=solve(N,L,move(V));
    if(t.size()==0&&p.size()==0)
        cout<<-1<<endl;
    else{
        for(auto [a,b]:t)
            cout<<(long long)a<<" "<<(long long)b<<"\n";
        for(int i:p)
            cout<<i<<" ";
        cout<<"\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 500 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 504 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 49 ms 6504 KB Output is correct
44 Incorrect 317 ms 46416 KB X_i is not increasing
45 Halted 0 ms 0 KB -