Submission #201269

#TimeUsernameProblemLanguageResultExecution timeMemory
201269dimash241Naan (JOI19_naan)C++17
100 / 100
880 ms138872 KiB
//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //# include <x86intrin.h> # include <bits/stdc++.h> # include <ext/pb_ds/assoc_container.hpp> # include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define _USE_MATH_DEFINES_ #define ll long long #define ld long double #define Accepted 0 #define pb push_back #define mp make_pair #define sz(x) (int)(x.size()) #define every(x) x.begin(),x.end() #define F first #define S second #define lb lower_bound #define ub upper_bound #define For(i,x,y) for (ll i = x; i <= y; i ++) #define FOr(i,x,y) for (ll i = x; i >= y; i --) #define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) // ROAD to... Red inline void Input_Output () { //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); } const double eps = 0.000001; const ld pi = acos(-1); const int maxn = 1e7 + 9; const int mod = 1e9 + 7; const ll MOD = 1e18 + 9; const ll INF = 1e18 + 123; const int inf = 2e9 + 11; const int mxn = 1e6 + 9; const int N = 2123; const int M = 22; const int pri = 997; const int Magic = 2101; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1}; using pt = pair<ll, ll>; int n, m, k; ll a[2020][2020]; ll pref[2020][2020]; ll s[2020]; vector < pt > ans; bool u[N]; vector < int > ord; int p[N]; pt reduc(pt a) { ll g = __gcd(a.F, a.S); a.F /= g; a.S /= g; return a; } pt val[N][N]; bool cmp (pt a, pt b) { return a.first * (ld)b.second < b.first * (ld)a.second; } int main () { SpeedForce; cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j], s[i] += a[i][j]; pref[i][j] = s[i]; } } for (int i = 1; i <= n; i ++) { int ptr = 0; val[i][0] = {0, 1}; ll cur = 0; for (int j = 1; j < n; ++j) { while (cur + a[i][ptr + 1] * (ll)n <= s[i] * j) { cur += a[i][++ptr] * (ll)n; } ll diff = s[i] * j - cur; pt fr = {diff, a[i][ptr + 1] * n}; fr.F += ptr * (ll)n * a[i][ptr + 1]; val[i][j] = reduc(fr); } val[i][n] = mp(m, 1); } for (int i = 1; i < n; ++i) { int pos = 1; while (u[pos]) ++pos; for (int j = pos + 1; j <= n; ++j) if (!u[j] && cmp(val[j][i], val[pos][i])) { pos = j; } u[pos] = 1; ord.pb(pos); ans.pb(val[pos][i]); } for (int i = 1; i <= n; i ++) if (!u[i]) ord.pb(i); for (auto it : ans) cout << it.F << ' ' << it.S << '\n'; for (auto it : ord) cout << it << ' '; cout << '\n'; return Accepted; } // B...a
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...