답안 #474153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474153	2021-09-17T02:57:17 Z	NhatMinh0208	Naan (JOI19_naan)	C++14	29 / 100	4000 ms	96316 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

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	62924 KB	Output is correct
2	Correct	33 ms	62920 KB	Output is correct
3	Correct	33 ms	62984 KB	Output is correct
4	Correct	32 ms	62972 KB	Output is correct
5	Correct	36 ms	62996 KB	Output is correct
6	Correct	35 ms	62924 KB	Output is correct
7	Correct	33 ms	62972 KB	Output is correct
8	Correct	33 ms	62916 KB	Output is correct
9	Correct	32 ms	62992 KB	Output is correct
10	Correct	32 ms	63032 KB	Output is correct
11	Correct	33 ms	63032 KB	Output is correct
12	Correct	33 ms	63032 KB	Output is correct
13	Correct	33 ms	62920 KB	Output is correct
14	Correct	33 ms	62940 KB	Output is correct
15	Correct	33 ms	62996 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	63040 KB	Output is correct
2	Correct	34 ms	62964 KB	Output is correct
3	Correct	35 ms	63040 KB	Output is correct
4	Correct	35 ms	63176 KB	Output is correct
5	Correct	34 ms	63012 KB	Output is correct
6	Correct	34 ms	62980 KB	Output is correct
7	Correct	32 ms	62988 KB	Output is correct
8	Correct	34 ms	62956 KB	Output is correct
9	Correct	33 ms	63052 KB	Output is correct
10	Correct	36 ms	63008 KB	Output is correct
11	Correct	33 ms	63000 KB	Output is correct
12	Correct	32 ms	62944 KB	Output is correct
13	Correct	33 ms	62944 KB	Output is correct
14	Correct	34 ms	63028 KB	Output is correct
15	Correct	36 ms	63044 KB	Output is correct
16	Correct	34 ms	63100 KB	Output is correct
17	Correct	34 ms	63076 KB	Output is correct
18	Correct	34 ms	63060 KB	Output is correct
19	Correct	36 ms	63024 KB	Output is correct
20	Correct	35 ms	63004 KB	Output is correct
21	Correct	35 ms	63068 KB	Output is correct
22	Correct	35 ms	63048 KB	Output is correct
23	Correct	33 ms	62980 KB	Output is correct
24	Correct	33 ms	63016 KB	Output is correct
25	Correct	33 ms	63052 KB	Output is correct
26	Correct	32 ms	62976 KB	Output is correct
27	Correct	35 ms	63108 KB	Output is correct

Subtask #3

0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	62924 KB	Output is correct
2	Correct	33 ms	62920 KB	Output is correct
3	Correct	33 ms	62984 KB	Output is correct
4	Correct	32 ms	62972 KB	Output is correct
5	Correct	36 ms	62996 KB	Output is correct
6	Correct	35 ms	62924 KB	Output is correct
7	Correct	33 ms	62972 KB	Output is correct
8	Correct	33 ms	62916 KB	Output is correct
9	Correct	32 ms	62992 KB	Output is correct
10	Correct	32 ms	63032 KB	Output is correct
11	Correct	33 ms	63032 KB	Output is correct
12	Correct	33 ms	63032 KB	Output is correct
13	Correct	33 ms	62920 KB	Output is correct
14	Correct	33 ms	62940 KB	Output is correct
15	Correct	33 ms	62996 KB	Output is correct
16	Correct	32 ms	63040 KB	Output is correct
17	Correct	34 ms	62964 KB	Output is correct
18	Correct	35 ms	63040 KB	Output is correct
19	Correct	35 ms	63176 KB	Output is correct
20	Correct	34 ms	63012 KB	Output is correct
21	Correct	34 ms	62980 KB	Output is correct
22	Correct	32 ms	62988 KB	Output is correct
23	Correct	34 ms	62956 KB	Output is correct
24	Correct	33 ms	63052 KB	Output is correct
25	Correct	36 ms	63008 KB	Output is correct
26	Correct	33 ms	63000 KB	Output is correct
27	Correct	32 ms	62944 KB	Output is correct
28	Correct	33 ms	62944 KB	Output is correct
29	Correct	34 ms	63028 KB	Output is correct
30	Correct	36 ms	63044 KB	Output is correct
31	Correct	34 ms	63100 KB	Output is correct
32	Correct	34 ms	63076 KB	Output is correct
33	Correct	34 ms	63060 KB	Output is correct
34	Correct	36 ms	63024 KB	Output is correct
35	Correct	35 ms	63004 KB	Output is correct
36	Correct	35 ms	63068 KB	Output is correct
37	Correct	35 ms	63048 KB	Output is correct
38	Correct	33 ms	62980 KB	Output is correct
39	Correct	33 ms	63016 KB	Output is correct
40	Correct	33 ms	63052 KB	Output is correct
41	Correct	32 ms	62976 KB	Output is correct
42	Correct	35 ms	63108 KB	Output is correct
43	Correct	422 ms	68824 KB	Output is correct
44	Correct	2483 ms	92056 KB	Output is correct
45	Correct	843 ms	81324 KB	Output is correct
46	Correct	95 ms	65984 KB	Output is correct
47	Correct	1487 ms	86164 KB	Output is correct
48	Correct	3458 ms	79048 KB	Output is correct
49	Correct	761 ms	71552 KB	Output is correct
50	Execution timed out	4070 ms	96316 KB	Time limit exceeded
51	Halted	0 ms	0 KB	-