Submission #474154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474154	2021-09-17T02:58:32 Z	NhatMinh0208	Naan (JOI19_naan)	C++14	29 / 100	137 ms	136388 KB

naan

#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;

//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif

class Fraction {
    long long numerator;
    long long denominator;
public:
    Fraction(long long n, long long d);
    Fraction();
    ~Fraction();
    Fraction operator+(const Fraction& f);
    Fraction operator-(const Fraction& f);
    Fraction operator*(const Fraction& f);
    Fraction operator/(const Fraction& f);
    Fraction operator+=(const Fraction& f);
    Fraction operator++();
    bool operator<(const Fraction& f);
    bool operator>(const Fraction& f);
    bool operator<=(const Fraction& f);
    bool operator>=(const Fraction& f);
    bool operator==(const Fraction& f);
    operator double();
    friend ostream &operator<<(ostream &output, const Fraction& f);

private:
    void simplify() {
        // reduction();
        fix_sign();
    }
    void fix_sign() {
        if (denominator < 0) {
            denominator = -denominator;
            numerator = -numerator;
        }
    }
    void reduction() {
        long long common = gcd(numerator, denominator);
        numerator /= common;
        denominator /= common;
    }
    long long gcd(long long x, long long y) {
        return y == 0 ? x : gcd(y, x % y);
    }
};

Fraction::Fraction(long long n, long long d) {
    if (d == 0) throw invalid_argument("d");
    numerator = n;
    denominator = d;
    simplify();
}


Fraction::Fraction() {
    numerator = 0;
    denominator = 1;
    simplify();
}

Fraction::~Fraction() {}

Fraction Fraction::operator+(const Fraction& f) {
    long long n = numerator * f.denominator + f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff;
}

Fraction Fraction::operator-(const Fraction& f) {
    long long n = numerator * f.denominator - f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff;
}

Fraction Fraction::operator*(const Fraction& f) {
    long long n = numerator * f.numerator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff;
}

Fraction Fraction::operator/(const Fraction& f) {
    long long n = numerator * f.denominator;
    long long d = denominator * f.numerator;

    Fraction ff(n, d);
    return ff;
}

Fraction Fraction::operator+=(const Fraction& f) {
    numerator = numerator * f.denominator + f.numerator * denominator;
    denominator = denominator * f.denominator;
    simplify();

    Fraction ff(numerator, denominator);
    return ff;
}

Fraction Fraction::operator++() {
    Fraction f(1, 1);
    numerator = numerator * f.denominator + f.numerator * denominator;
    denominator = denominator * f.denominator;
    simplify();

    Fraction ff(numerator, denominator);
    return ff;
}

bool Fraction::operator<(const Fraction& f) {
    long long n = numerator * f.denominator - f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff.numerator < 0;
}


bool Fraction::operator>(const Fraction& f) {
    long long n = numerator * f.denominator - f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff.numerator > 0;
}


bool Fraction::operator<=(const Fraction& f) {
    long long n = numerator * f.denominator - f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff.numerator <= 0;
}


bool Fraction::operator>=(const Fraction& f) {
    long long n = numerator * f.denominator - f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff.numerator >= 0;
}

bool Fraction::operator==(const Fraction& f) {
    long long n = numerator * f.denominator - f.numerator * denominator;
    long long d = denominator * f.denominator;

    Fraction ff(n, d);
    return ff.denominator == 0;
}

Fraction::operator double() {
    return (double)numerator / denominator;
}

ostream &operator<<(ostream &output, const Fraction& f) {
    output << "" << f.numerator << " " << f.denominator << "";
    return output;
}


int used[2001];
vector<ll> p;
ll n,m,i,j,k,t,t1,u,v,a,b;
ll w[2001][2001];
Fraction lul[2001][2001];
int main()
{
	fio;
    cin>>n>>m;
    for (i=0;i<n;i++) for (j=0;j<m;j++) {
        cin>>w[i][j];
    }
    for (i=0;i<n;i++) {
        u=0;
        for (j=0;j<m;j++) u+=w[i][j];
        int raw=0;
        Fraction frac(0,1);
        Fraction balance(0,1);
        for (t=1;t<=n;t++) {
            balance+=Fraction(u,n);
            while(true) {
                if (balance<=(Fraction(1,1)-frac)*Fraction(w[i][raw],1)) {
                    frac+=balance/Fraction(w[i][raw],1);
                    balance=Fraction(0,1);
                    lul[i][t]=frac+Fraction(raw,1);
                    // cout<<lul[i][t]<<' ';
                    break;
                } else {
                    balance=balance-(Fraction(1,1)-frac)*Fraction(w[i][raw],1);
                    frac=Fraction(0,1);
                    raw++;
                }
            }
        }
        // cout<<endl;
    }
    for (i=0;i<n;i++) {
        Fraction mn(m+1,1);
        a=0;
        for (j=0;j<n;j++) if (!used[j] && lul[j][i+1]<mn) {
            mn=lul[j][i+1];
            a=j;
        }
        if (i<n-1) cout<<mn<<endl;
        p.push_back(a);
        used[a]=1;
    }
    for (auto g : p) cout<<g+1<<' ';    
}
// if (i<n-1)

Compilation message

naan.cpp:23: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
   23 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	62924 KB	Output is correct
2	Correct	34 ms	62908 KB	Output is correct
3	Correct	33 ms	62916 KB	Output is correct
4	Correct	34 ms	63012 KB	Output is correct
5	Correct	33 ms	63004 KB	Output is correct
6	Correct	33 ms	62888 KB	Output is correct
7	Correct	33 ms	62924 KB	Output is correct
8	Correct	35 ms	63012 KB	Output is correct
9	Correct	34 ms	62888 KB	Output is correct
10	Correct	33 ms	62916 KB	Output is correct
11	Correct	33 ms	62916 KB	Output is correct
12	Correct	33 ms	63004 KB	Output is correct
13	Correct	33 ms	62896 KB	Output is correct
14	Correct	35 ms	62912 KB	Output is correct
15	Correct	33 ms	63008 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	62924 KB	Output is correct
2	Correct	32 ms	63020 KB	Output is correct
3	Correct	34 ms	63080 KB	Output is correct
4	Correct	34 ms	63020 KB	Output is correct
5	Correct	33 ms	63076 KB	Output is correct
6	Correct	34 ms	63040 KB	Output is correct
7	Correct	34 ms	62948 KB	Output is correct
8	Correct	32 ms	63040 KB	Output is correct
9	Correct	34 ms	62992 KB	Output is correct
10	Correct	34 ms	63172 KB	Output is correct
11	Correct	33 ms	62992 KB	Output is correct
12	Correct	33 ms	62924 KB	Output is correct
13	Correct	33 ms	62996 KB	Output is correct
14	Correct	34 ms	63056 KB	Output is correct
15	Correct	33 ms	63012 KB	Output is correct
16	Correct	34 ms	63000 KB	Output is correct
17	Correct	33 ms	63028 KB	Output is correct
18	Correct	34 ms	62976 KB	Output is correct
19	Correct	33 ms	63020 KB	Output is correct
20	Correct	35 ms	62996 KB	Output is correct
21	Correct	35 ms	62964 KB	Output is correct
22	Correct	34 ms	63084 KB	Output is correct
23	Correct	33 ms	62984 KB	Output is correct
24	Correct	33 ms	63044 KB	Output is correct
25	Correct	34 ms	63028 KB	Output is correct
26	Correct	34 ms	62972 KB	Output is correct
27	Correct	35 ms	63060 KB	Output is correct

Subtask #3

0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	62924 KB	Output is correct
2	Correct	34 ms	62908 KB	Output is correct
3	Correct	33 ms	62916 KB	Output is correct
4	Correct	34 ms	63012 KB	Output is correct
5	Correct	33 ms	63004 KB	Output is correct
6	Correct	33 ms	62888 KB	Output is correct
7	Correct	33 ms	62924 KB	Output is correct
8	Correct	35 ms	63012 KB	Output is correct
9	Correct	34 ms	62888 KB	Output is correct
10	Correct	33 ms	62916 KB	Output is correct
11	Correct	33 ms	62916 KB	Output is correct
12	Correct	33 ms	63004 KB	Output is correct
13	Correct	33 ms	62896 KB	Output is correct
14	Correct	35 ms	62912 KB	Output is correct
15	Correct	33 ms	63008 KB	Output is correct
16	Correct	32 ms	62924 KB	Output is correct
17	Correct	32 ms	63020 KB	Output is correct
18	Correct	34 ms	63080 KB	Output is correct
19	Correct	34 ms	63020 KB	Output is correct
20	Correct	33 ms	63076 KB	Output is correct
21	Correct	34 ms	63040 KB	Output is correct
22	Correct	34 ms	62948 KB	Output is correct
23	Correct	32 ms	63040 KB	Output is correct
24	Correct	34 ms	62992 KB	Output is correct
25	Correct	34 ms	63172 KB	Output is correct
26	Correct	33 ms	62992 KB	Output is correct
27	Correct	33 ms	62924 KB	Output is correct
28	Correct	33 ms	62996 KB	Output is correct
29	Correct	34 ms	63056 KB	Output is correct
30	Correct	33 ms	63012 KB	Output is correct
31	Correct	34 ms	63000 KB	Output is correct
32	Correct	33 ms	63028 KB	Output is correct
33	Correct	34 ms	62976 KB	Output is correct
34	Correct	33 ms	63020 KB	Output is correct
35	Correct	35 ms	62996 KB	Output is correct
36	Correct	35 ms	62964 KB	Output is correct
37	Correct	34 ms	63084 KB	Output is correct
38	Correct	33 ms	62984 KB	Output is correct
39	Correct	33 ms	63044 KB	Output is correct
40	Correct	34 ms	63028 KB	Output is correct
41	Correct	34 ms	62972 KB	Output is correct
42	Correct	35 ms	63060 KB	Output is correct
43	Runtime error	137 ms	136388 KB	Execution killed with signal 6
44	Halted	0 ms	0 KB	-