Submission #474161

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474161	2021-09-17T04:01:52 Z	NhatMinh0208	Naan (JOI19_naan)	C++17	29 / 100	312 ms	90856 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 {

public:
    long long numerator;
    long long denominator;
    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);
 
    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];
        ll raw=0;
        ll frac=0;
        ll balance=0;
        for (t=1;t<=n;t++) {
            balance+=u;
            while(true) {
                if (balance<=(w[i][raw]*n-frac)) {
                    frac+=balance;
                    balance=0;
                    lul[i][t]=Fraction(raw*w[i][raw]*n+frac,w[i][raw]*n);
                    // cout<<lul[i][t]<<' ';
                    break;
                } else {
                    balance=balance-(w[i][raw]*n-frac);
                    frac=0;
                    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	34 ms	62916 KB	Output is correct
2	Correct	34 ms	62988 KB	Output is correct
3	Correct	35 ms	62916 KB	Output is correct
4	Correct	35 ms	63048 KB	Output is correct
5	Correct	35 ms	62916 KB	Output is correct
6	Correct	33 ms	62924 KB	Output is correct
7	Correct	34 ms	62940 KB	Output is correct
8	Correct	33 ms	63024 KB	Output is correct
9	Correct	35 ms	62972 KB	Output is correct
10	Correct	35 ms	62996 KB	Output is correct
11	Correct	36 ms	62924 KB	Output is correct
12	Correct	38 ms	62916 KB	Output is correct
13	Correct	35 ms	62932 KB	Output is correct
14	Correct	34 ms	63004 KB	Output is correct
15	Correct	39 ms	63000 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	62916 KB	Output is correct
2	Correct	35 ms	62972 KB	Output is correct
3	Correct	38 ms	62988 KB	Output is correct
4	Correct	34 ms	63056 KB	Output is correct
5	Correct	33 ms	62988 KB	Output is correct
6	Correct	35 ms	63052 KB	Output is correct
7	Correct	39 ms	63060 KB	Output is correct
8	Correct	33 ms	62916 KB	Output is correct
9	Correct	36 ms	62984 KB	Output is correct
10	Correct	35 ms	63052 KB	Output is correct
11	Correct	34 ms	62988 KB	Output is correct
12	Correct	34 ms	62980 KB	Output is correct
13	Correct	34 ms	63008 KB	Output is correct
14	Correct	35 ms	63020 KB	Output is correct
15	Correct	35 ms	63096 KB	Output is correct
16	Correct	34 ms	63044 KB	Output is correct
17	Correct	34 ms	63036 KB	Output is correct
18	Correct	35 ms	63004 KB	Output is correct
19	Correct	37 ms	62968 KB	Output is correct
20	Correct	36 ms	63044 KB	Output is correct
21	Correct	36 ms	63000 KB	Output is correct
22	Correct	36 ms	63136 KB	Output is correct
23	Correct	33 ms	62880 KB	Output is correct
24	Correct	34 ms	62988 KB	Output is correct
25	Correct	39 ms	63044 KB	Output is correct
26	Correct	34 ms	62900 KB	Output is correct
27	Correct	34 ms	62976 KB	Output is correct

Subtask #3

0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	62916 KB	Output is correct
2	Correct	34 ms	62988 KB	Output is correct
3	Correct	35 ms	62916 KB	Output is correct
4	Correct	35 ms	63048 KB	Output is correct
5	Correct	35 ms	62916 KB	Output is correct
6	Correct	33 ms	62924 KB	Output is correct
7	Correct	34 ms	62940 KB	Output is correct
8	Correct	33 ms	63024 KB	Output is correct
9	Correct	35 ms	62972 KB	Output is correct
10	Correct	35 ms	62996 KB	Output is correct
11	Correct	36 ms	62924 KB	Output is correct
12	Correct	38 ms	62916 KB	Output is correct
13	Correct	35 ms	62932 KB	Output is correct
14	Correct	34 ms	63004 KB	Output is correct
15	Correct	39 ms	63000 KB	Output is correct
16	Correct	33 ms	62916 KB	Output is correct
17	Correct	35 ms	62972 KB	Output is correct
18	Correct	38 ms	62988 KB	Output is correct
19	Correct	34 ms	63056 KB	Output is correct
20	Correct	33 ms	62988 KB	Output is correct
21	Correct	35 ms	63052 KB	Output is correct
22	Correct	39 ms	63060 KB	Output is correct
23	Correct	33 ms	62916 KB	Output is correct
24	Correct	36 ms	62984 KB	Output is correct
25	Correct	35 ms	63052 KB	Output is correct
26	Correct	34 ms	62988 KB	Output is correct
27	Correct	34 ms	62980 KB	Output is correct
28	Correct	34 ms	63008 KB	Output is correct
29	Correct	35 ms	63020 KB	Output is correct
30	Correct	35 ms	63096 KB	Output is correct
31	Correct	34 ms	63044 KB	Output is correct
32	Correct	34 ms	63036 KB	Output is correct
33	Correct	35 ms	63004 KB	Output is correct
34	Correct	37 ms	62968 KB	Output is correct
35	Correct	36 ms	63044 KB	Output is correct
36	Correct	36 ms	63000 KB	Output is correct
37	Correct	36 ms	63136 KB	Output is correct
38	Correct	33 ms	62880 KB	Output is correct
39	Correct	34 ms	62988 KB	Output is correct
40	Correct	39 ms	63044 KB	Output is correct
41	Correct	34 ms	62900 KB	Output is correct
42	Correct	34 ms	62976 KB	Output is correct
43	Correct	63 ms	67252 KB	Output is correct
44	Correct	236 ms	81964 KB	Output is correct
45	Correct	168 ms	73796 KB	Output is correct
46	Correct	62 ms	64792 KB	Output is correct
47	Correct	185 ms	78052 KB	Output is correct
48	Correct	141 ms	77196 KB	Output is correct
49	Correct	81 ms	70468 KB	Output is correct
50	Incorrect	312 ms	90856 KB	X_i is not increasing
51	Halted	0 ms	0 KB	-