oj.uz

답안 #375195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375195 2021-03-09T04:14:02 Z wiwiho Naan (JOI19_naan) C++14
29 / 100
 4000 ms 1388 KB 
#include <bits/stdc++.h>
 
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
using pll = pair<ll, ll>;

struct frac{
    ll a, b;
    frac(ll a = 0, ll b = 1): a(a), b(b) {
    }
    void qaq(){
        if(b < 0) b *= -1, a *= -1;
        ll g = __gcd(a, b);
        a /= g;
        b /= g;
    }
};

frac operator+(frac f1, frac f2){
    ll g = __gcd(f1.b, f2.b);
    return frac(f1.a * (f2.b / g) + f2.a * (f1.b / g), f1.b * f2.b / g);
}
frac operator*(frac f1, frac f2){
    return frac(f1.a * f2.a, f1.b * f2.b);
}
frac operator/(frac f1, frac f2){
    return f1 * frac(f2.b, f2.a);
}
frac operator-(frac f1, frac f2){
    return f1 + frac(-f2.a, f2.b);
}
frac operator+=(frac& f1, frac f2){
    return f1 = f1 + f2;
}
frac operator-=(frac& f1, frac f2){
    return f1 = f1 - f2;
}
bool operator<=(frac f1, frac f2){
    ll g = __gcd(f1.b, f2.b);
    return f1.a * (f2.b / g) <= f2.a * (f1.b / g);
}
bool operator==(frac f1, frac f2){
    f1.qaq();
    f2.qaq();
    return f1.a == f2.a && f1.b == f2.b;
}
ostream& operator<<(ostream& o, frac f){
    return o << f.a << '/' << f.b;
}

int n, l;
vector<vector<int>> v;

vector<frac> check(vector<int>& p){
    //cerr << "test ";
    //printv(p, cerr);
    
    int lst = 0;
    frac r(1);
    vector<frac> ans;
    for(int i : p){
    
        frac total = frac(0, 1);
        for(int j = 0; j < l; j++){
            total += frac(v[i][j], 1);
        }
        frac need = total / n;

        while(need.a != 0 && lst < l){
            //cerr << i << " " << lst << " " << r << " " << need << "\n";
            if(r.a == 0){
                r = 1;
                lst++;
                continue;
            }
            if(v[i][lst] * r <= need){
                //cerr << "test1 " << v[i][lst] * r << "\n";
                need -= v[i][lst] * r;
                r = 1;
                lst++;
                continue;
            }
            
            r -= need / v[i][lst];
            need = 0;
        }

        if(need == 0){
            //cerr << "ok " << frac(lst) + 1 - r << "\n";
            ans.eb(frac(lst) + 1 - r);
        }
        else return vector<frac>();
        
    }

    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> l;
    v.resize(n + 1, vector<int>(l));
    vector<int> p(n);
    for(int i = 1; i <= n; i++){
        p[i - 1] = i;
        for(int j = 0; j < l; j++) cin >> v[i][j];
    }

    do{
        vector<frac> ans = check(p);
        if(ans.empty()) continue;
        for(int j = 0; j < n - 1; j++){
            frac i = ans[j];
            cout << i.a << " " << i.b << "\n";
        }
        printv(p, cout);
        return 0;
    }
    while(next_permutation(iter(p)));

    cout << "-1\n";

    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 3 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 2 ms 364 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 1 ms 364 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Execution timed out 4053 ms 1388 KB Time limit exceeded
44 Halted 0 ms 0 KB -