답안 #474158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474158	2021-09-17T03:21:02 Z	NhatMinh0208	Naan (JOI19_naan)	C++17	29 / 100	2237 ms	90984 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() {
        if (abs(numerator)>1e9 || abs(denominator)>1e9) 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(to_string(n));}
    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	35 ms	62872 KB	Output is correct
2	Correct	32 ms	62932 KB	Output is correct
3	Correct	33 ms	62952 KB	Output is correct
4	Correct	32 ms	62952 KB	Output is correct
5	Correct	33 ms	62912 KB	Output is correct
6	Correct	33 ms	62916 KB	Output is correct
7	Correct	35 ms	63052 KB	Output is correct
8	Correct	40 ms	63012 KB	Output is correct
9	Correct	34 ms	62920 KB	Output is correct
10	Correct	38 ms	62956 KB	Output is correct
11	Correct	33 ms	62924 KB	Output is correct
12	Correct	34 ms	62896 KB	Output is correct
13	Correct	35 ms	62924 KB	Output is correct
14	Correct	32 ms	62924 KB	Output is correct
15	Correct	35 ms	62912 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	62916 KB	Output is correct
2	Correct	34 ms	63032 KB	Output is correct
3	Correct	35 ms	63064 KB	Output is correct
4	Correct	39 ms	63072 KB	Output is correct
5	Correct	35 ms	63044 KB	Output is correct
6	Correct	34 ms	63028 KB	Output is correct
7	Correct	34 ms	62904 KB	Output is correct
8	Correct	35 ms	62992 KB	Output is correct
9	Correct	41 ms	63056 KB	Output is correct
10	Correct	34 ms	63040 KB	Output is correct
11	Correct	39 ms	62960 KB	Output is correct
12	Correct	34 ms	62904 KB	Output is correct
13	Correct	34 ms	63000 KB	Output is correct
14	Correct	35 ms	63044 KB	Output is correct
15	Correct	34 ms	62980 KB	Output is correct
16	Correct	38 ms	63052 KB	Output is correct
17	Correct	35 ms	63012 KB	Output is correct
18	Correct	35 ms	63044 KB	Output is correct
19	Correct	35 ms	62976 KB	Output is correct
20	Correct	37 ms	63132 KB	Output is correct
21	Correct	42 ms	63052 KB	Output is correct
22	Correct	35 ms	63040 KB	Output is correct
23	Correct	34 ms	62980 KB	Output is correct
24	Correct	35 ms	63044 KB	Output is correct
25	Correct	35 ms	62988 KB	Output is correct
26	Correct	34 ms	63036 KB	Output is correct
27	Correct	34 ms	63060 KB	Output is correct

Subtask #3

0 / 71.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	62872 KB	Output is correct
2	Correct	32 ms	62932 KB	Output is correct
3	Correct	33 ms	62952 KB	Output is correct
4	Correct	32 ms	62952 KB	Output is correct
5	Correct	33 ms	62912 KB	Output is correct
6	Correct	33 ms	62916 KB	Output is correct
7	Correct	35 ms	63052 KB	Output is correct
8	Correct	40 ms	63012 KB	Output is correct
9	Correct	34 ms	62920 KB	Output is correct
10	Correct	38 ms	62956 KB	Output is correct
11	Correct	33 ms	62924 KB	Output is correct
12	Correct	34 ms	62896 KB	Output is correct
13	Correct	35 ms	62924 KB	Output is correct
14	Correct	32 ms	62924 KB	Output is correct
15	Correct	35 ms	62912 KB	Output is correct
16	Correct	35 ms	62916 KB	Output is correct
17	Correct	34 ms	63032 KB	Output is correct
18	Correct	35 ms	63064 KB	Output is correct
19	Correct	39 ms	63072 KB	Output is correct
20	Correct	35 ms	63044 KB	Output is correct
21	Correct	34 ms	63028 KB	Output is correct
22	Correct	34 ms	62904 KB	Output is correct
23	Correct	35 ms	62992 KB	Output is correct
24	Correct	41 ms	63056 KB	Output is correct
25	Correct	34 ms	63040 KB	Output is correct
26	Correct	39 ms	62960 KB	Output is correct
27	Correct	34 ms	62904 KB	Output is correct
28	Correct	34 ms	63000 KB	Output is correct
29	Correct	35 ms	63044 KB	Output is correct
30	Correct	34 ms	62980 KB	Output is correct
31	Correct	38 ms	63052 KB	Output is correct
32	Correct	35 ms	63012 KB	Output is correct
33	Correct	35 ms	63044 KB	Output is correct
34	Correct	35 ms	62976 KB	Output is correct
35	Correct	37 ms	63132 KB	Output is correct
36	Correct	42 ms	63052 KB	Output is correct
37	Correct	35 ms	63040 KB	Output is correct
38	Correct	34 ms	62980 KB	Output is correct
39	Correct	35 ms	63044 KB	Output is correct
40	Correct	35 ms	62988 KB	Output is correct
41	Correct	34 ms	63036 KB	Output is correct
42	Correct	34 ms	63060 KB	Output is correct
43	Correct	235 ms	67304 KB	Output is correct
44	Correct	1233 ms	81896 KB	Output is correct
45	Correct	415 ms	73796 KB	Output is correct
46	Correct	64 ms	64832 KB	Output is correct
47	Correct	727 ms	78068 KB	Output is correct
48	Correct	1840 ms	77432 KB	Output is correct
49	Correct	384 ms	70468 KB	Output is correct
50	Incorrect	2237 ms	90984 KB	X_i is not increasing
51	Halted	0 ms	0 KB	-