Submission #375175

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375175	2021-03-09T04:01:12 Z	wiwiho	Naan (JOI19_naan)	C++14	0 / 100	2 ms	640 KB

naan

#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){
    f1 = f1 + f2;
}
frac operator-=(frac& f1, frac f2){
    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 = 0;
        for(int j = 0; j < l; j++) total += v[i][j];
        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;
        assert(ans.size() == n);
        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;
}

Compilation message

naan.cpp: In function 'frac operator+=(frac&, frac)':
naan.cpp:45:1: warning: no return statement in function returning non-void [-Wreturn-type]
   45 | }
      | ^
naan.cpp: In function 'frac operator-=(frac&, frac)':
naan.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
   48 | }
      | ^
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from naan.cpp:1:
naan.cpp: In function 'int main()':
naan.cpp:122:27: warning: comparison of integer expressions of different signedness: 'std::vector<frac>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |         assert(ans.size() == n);
      |                ~~~~~~~~~~~^~~~

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	640 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	492 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	640 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-