QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141452 | #5280. Depot Rearrangement | PCTprobability# | 95 | 159ms | 45592kb | C++14 | 9.3kb | 2023-08-17 13:46:21 | 2024-07-04 01:46:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define endl "\n"
typedef pair<int, int> Pii;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(x) begin(x), end(x)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(s) (s).begin(),(s).end()
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define se second
#define pb push_back
#define P pair<ll,ll>
#define PQminll priority_queue<ll, vector<ll>, greater<ll>>
#define PQmaxll priority_queue<ll,vector<ll>,less<ll>>
#define PQminP priority_queue<P, vector<P>, greater<P>>
#define PQmaxP priority_queue<P,vector<P>,less<P>>
#define NP next_permutation
//const ll mod = 1000000009;
//const ll mod = 998244353;
const ll mod = 1000000007;
const ll inf = 4100000000000000000ll;
const ld eps = ld(0.00000000001);
static const long double pi = 3.141592653589793;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
template<class T>auto min(const T& a){ return *min_element(all(a)); }
template<class T>auto max(const T& a){ return *max_element(all(a)); }
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>bool chmax(T &a,const T b) { if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a,const T b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;}
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}
P hyou(P a){ll x=fastgcd(abs(a.fi),abs(a.se));a.fi/=x;a.se/=x;if(a.se<0){a.fi*=-1;a.se*=-1;}return a;}
P Pplus(P a,P b){ return hyou({a.fi*b.se+b.fi*a.se,a.se*b.se});}
P Ptimes(P a,ll b){ return hyou({a.fi*b,a.se});}
P Ptimes(P a,P b){ return hyou({a.fi*b.fi,a.se*b.se});}
P Pminus(P a,P b){ return hyou({a.fi*b.se-b.fi*a.se,a.se*b.se});}
P Pgyaku(P a){ return hyou({a.se,a.fi});}
void cincout(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout<< fixed << setprecision(15);
}
struct UnionFind{
vector<ll> sz,rt;
UnionFind(ll n){
sz.resize(n);
rt.resize(n);
for(int i=0;i<n;i++){
sz[i]=1;
rt[i]=i;
}
}
ll root(ll x){
while(x!=rt[x]){
x=rt[x]=rt[rt[x]];
}
return x;
}
ll size(ll x){
return sz[root(x)];
}
bool merge(ll a,ll b){
a=root(a);
b=root(b);
if(a==b) return false;
if(sz[a]<sz[b]) swap(a,b);
sz[a]+=sz[b];
rt[b]=a;
return true;
}
};
P p[200000],q[200000];
vector<ll> pf[200000],qf[200000],ps[200000],qs[200000];
P pid[200000],qid[200000];
bool sp[200000],sq[200000];
ll qb[200000];
int main(){
cincout();
ll n,m;
cin>>n>>m;
vector<vector<ll>> a(n,vector<ll>(m));
ll x=0,y=0;
UnionFind g(m);
ll cnt=0;
for(int i=0;i<n;i++){
vcin(a[i]);
for(auto &e:a[i]) e--;
vector<vector<ll>> c(m);
for(int j=0;j<m;j++){
c[a[i][j]].pb(i*m+j);
}
for(int j=0;j<m;j++){
if(c[j].size()==0){
p[x]={i,j};
pf[i].pb(x);
ps[j].pb(x);
x++;
cnt++;
}
else{
for(int k=1;k<c[j].size();k++){
q[y]={i,j};
qb[y]=c[j][k];
qf[i].pb(y);
qs[j].pb(y);
y++;
}
}
}
for(int j=0;j<m;j++){
for(int k=0;k<m;k++){
if(c[j].size()==0&&c[k].size()>=2){
g.merge(j,k);
}
}
}
}
ll msz=0;
for(int i=0;i<m;i++){
if(g.size(i)>=2&&g.root(i)==i){
msz++;
}
}
UnionFind t(x+y);
for(int i=0;i<max(n,m);i++){
//pf と qf を適当に結ぶ]
// cout<<i<<" "<<pf[i].size()<<" "<<ps[i].size()<<endl;
// cout<<"f"<<endl;
for(int j=0;j<pf[i].size();j++){
// cout<<pf[i][j]<<" "<<qf[i][j]<<endl;
t.merge(pf[i][j],qf[i][j]+x);
pid[pf[i][j]].fi=qf[i][j];
qid[qf[i][j]].fi=pf[i][j];
}
//ps と qs を適当に結ぶ
// cout<<"s"<<endl;
for(int j=0;j<ps[i].size();j++){
// cout<<ps[i][j]<<" "<<qs[i][j]<<endl;
t.merge(ps[i][j],qs[i][j]+x);
pid[ps[i][j]].se=qs[i][j];
qid[qs[i][j]].se=ps[i][j];
}
}
ll sz=0;
// cout<<x<<" "<<y<<endl;
for(int i=0;i<x+y;i++) if(t.root(i)==i) sz++;
// cout<<sz<<endl;
while(sz!=msz){
//pf[i] のうち、異なる連結成分に属するものがあったら 2 個の pid.fi を swap する
for(int i=0;i<n;i++){
if(pf[i].size()==0) continue;
vector<P> r;
vector<ll> id;
for(auto e:pf[i]){
r.pb({t.root(e),e});
}
sor(r);
for(int j=0;j<r.size();j++){
if(j==0||r[j].fi!=r[j-1].fi) id.pb(r[j].se);
}
if(id.size()>=2){
for(int j=0;j+1<id.size();j++){
swap(pid[id[j]].fi,pid[id[j+1]].fi);
swap(qid[pid[id[j]].fi].fi,qid[pid[id[j+1]].fi].fi);
t.merge(id[j],id[j+1]);
sz--;
}
}
}
//ps[i] のうち、異なる連結成分に属するものがあったら 2 個の pid.se を swap する
for(int i=0;i<m;i++){
if(ps[i].size()==0) continue;
vector<P> r;
vector<ll> id;
for(auto e:ps[i]){
r.pb({t.root(e),e});
}
sor(r);
for(int j=0;j<r.size();j++){
if(j==0||r[j].fi!=r[j-1].fi) id.pb(r[j].se);
}
if(id.size()>=2){
for(int j=0;j+1<id.size();j++){
swap(pid[id[j]].se,pid[id[j+1]].se);
swap(qid[pid[id[j]].se].se,qid[pid[id[j+1]].se].se);
t.merge(id[j],id[j+1]);
sz--;
}
}
}
//qf[i] のうち、異なる連結成分に属するものがあったら 2 個の qid.fi を swap する
for(int i=0;i<n;i++){
if(qf[i].size()==0) continue;
vector<P> r;
vector<ll> id;
for(auto e:qf[i]){
r.pb({t.root(e+x),e});
}
sor(r);
for(int j=0;j<r.size();j++){
if(j==0||r[j].fi!=r[j-1].fi) id.pb(r[j].se);
}
if(id.size()>=2){
for(int j=0;j+1<id.size();j++){
swap(qid[id[j]].fi,qid[id[j+1]].fi);
swap(pid[qid[id[j]].fi].fi,pid[qid[id[j+1]].fi].fi);
t.merge(id[j]+x,id[j+1]+x);
sz--;
}
}
}
//qs[i] のうち、異なる連結成分に属するものがあったら 2 個の qid.se を swap する
for(int i=0;i<m;i++){
if(qs[i].size()==0) continue;
vector<P> r;
vector<ll> id;
for(auto e:qs[i]){
r.pb({t.root(e+x),e});
}
sor(r);
for(int j=0;j<r.size();j++){
if(j==0||r[j].fi!=r[j-1].fi) id.pb(r[j].se);
}
if(id.size()>=2){
for(int j=0;j+1<id.size();j++){
swap(qid[id[j]].se,qid[id[j+1]].se);
swap(pid[qid[id[j]].se].se,pid[qid[id[j+1]].se].se);
t.merge(id[j]+x,id[j+1]+x);
sz--;
}
}
}
}
cout<<cnt+sz<<endl;
for(int i=0;i<x;i++){
if(!sp[i]){
int v=i;
int v2=n*m+1;
while(true){
sp[v]=true;
v=pid[v].se;
cout<<qb[v]+1<<" "<<v2<<endl;
v2=qb[v]+1;
v=qid[v].fi;
if(v==i) break;
}
cout<<n*m+1<<" "<<v2<<endl;
}
}
}
詳細信息
Test #1:
score: 5
Accepted
time: 6ms
memory: 24108kb
input:
10 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
output:
0
result:
Test #2:
score: 0
Checker Judgement Failed
input:
5 4 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4
output:
13 7 21 14 7 3 14 12 3 20 12 15 20 8 15 19 8 10 19 2 10 18 2 4 18 21 4
result:
Test #3:
score: 5
Accepted
time: 6ms
memory: 30128kb
input:
10 10 8 10 10 3 7 3 5 6 1 4 3 8 2 9 1 8 4 2 7 3 10 7 9 2 1 10 10 9 1 2 9 7 4 5 2 9 10 5 7 6 6 8 6 8 4 2 9 1 2 8 6 1 4 2 2 1 5 6 3 10 10 7 9 4 8 9 8 2 5 6 4 3 1 6 3 3 10 7 7 5 3 6 8 5 9 4 6 7 9 4 10 5 3 4 5 1 1 7 8 5
output:
32 18 101 38 18 29 38 6 29 28 6 95 28 87 95 49 87 75 49 30 75 90 30 97 90 55 97 79 55 66 79 76 66 67 76 56 67 50 56 26 50 58 26 36 58 44 36 39 44 20 39 43 20 100 43 89 100 27 89 16 27 3 16 101 3
result:
ok both subtasks are correct!
Test #4:
score: 5
Accepted
time: 7ms
memory: 30280kb
input:
100 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 9 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10...
output:
19 453 1001 184 453 734 184 713 734 819 713 949 819 359 949 775 359 175 775 210 175 830 210 670 830 850 670 814 850 109 814 1001 109 747 1001 707 747 1001 707
result:
ok both subtasks are correct!
Test #5:
score: 5
Accepted
time: 8ms
memory: 30684kb
input:
200 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
195 5773 20001 7068 5773 18968 7068 19768 18968 6955 19768 16555 6955 4647 16555 9473 4647 14335 9473 15140 14335 14098 15140 16998 14098 17052 16998 16952 17052 6129 16952 17229 6129 19529 17229 18829 19529 19747 18829 10354 19747 7854 10354 459 7854 3259 459 1459 3259 5159 1459 1862 5159 3192 1862...
result:
ok both subtasks are correct!
Test #6:
score: 5
Accepted
time: 4ms
memory: 30604kb
input:
201 20 20 18 5 5 1 7 8 17 12 10 20 12 13 19 16 2 9 8 20 20 19 10 17 20 9 11 15 17 9 2 3 4 17 10 7 20 7 19 17 11 20 2 1 13 11 9 11 6 10 8 11 3 2 16 9 15 16 12 13 6 5 13 4 13 3 8 20 18 10 3 14 1 11 20 17 17 2 11 20 1 4 10 3 3 9 13 7 10 19 16 14 16 9 19 14 15 12 9 20 12 2 19 18 2 7 7 2 12 10 8 20 18 16...
output:
1401 70 4021 106 70 262 106 194 262 313 194 384 313 217 384 187 217 358 187 259 358 55 259 37 55 57 37 38 57 80 38 153 80 510 153 265 510 428 265 374 428 303 374 171 303 296 171 429 296 649 429 333 649 633 333 190 633 136 190 51 136 28 51 12 28 60 12 149 60 78 149 29 78 4 29 140 4 231 140 193 231 33...
result:
ok both subtasks are correct!
Test #7:
score: 5
Accepted
time: 47ms
memory: 30896kb
input:
300 300 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
205 72662 90001 75733 72662 37143 75733 68130 37143 51930 68130 46595 51930 47192 46595 14663 47192 6563 14663 7163 6563 78731 7163 7031 78731 47363 7031 83192 47363 52980 83192 19980 52980 63494 19980 33143 63494 63443 33143 34499 63443 26699 34499 67162 26699 23362 67162 56062 23362 63562 56062 19...
result:
ok both subtasks are correct!
Test #8:
score: 5
Accepted
time: 13ms
memory: 31152kb
input:
301 40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
11624 303 12041 6631 303 9202 6631 227 9202 7833 227 9833 7833 9576 9833 4455 9576 4020 4455 5824 4020 7075 5824 10418 7075 5076 10418 10665 5076 7189 10665 8614 7189 3826 8614 7323 3826 782 7323 6343 782 6785 6343 7700 6785 5609 7700 2244 5609 652 2244 3330 652 2486 3330 1262 2486 6354 1262 10096 6...
result:
ok both subtasks are correct!
Test #9:
score: 5
Accepted
time: 20ms
memory: 33748kb
input:
400 100 11 65 1 79 15 18 79 46 9 30 71 53 58 55 94 73 39 16 6 91 49 30 23 30 28 81 90 48 97 54 79 30 94 18 42 77 44 36 5 48 55 97 79 36 41 59 79 71 32 59 3 10 63 52 44 41 9 46 31 31 56 87 60 80 12 51 15 78 41 65 95 34 29 83 46 64 37 53 98 17 41 45 36 73 20 53 48 80 57 54 57 72 39 56 98 6 10 78 11 72...
output:
14592 196 40001 900 196 1043 900 1771 1043 639 1771 2037 639 3390 2037 2690 3390 1931 2690 3200 1931 3625 3200 3472 3625 4918 3472 2732 4918 4577 2732 6670 4577 8096 6670 7193 8096 6171 7193 5490 6171 7686 5490 7089 7686 5678 7089 5531 5678 7475 5531 6371 7475 5981 6371 6571 5981 6147 6571 5142 6147...
result:
ok both subtasks are correct!
Test #10:
score: 5
Accepted
time: 3ms
memory: 30688kb
input:
40 160 17 2 3 4 5 6 7 91 9 10 154 12 103 14 15 16 17 25 19 58 21 8 23 24 52 26 27 58 120 105 50 55 104 32 35 36 37 38 45 10 41 42 43 44 45 71 47 48 49 34 140 52 53 54 115 44 28 58 59 60 61 62 63 64 132 66 67 68 69 70 71 69 24 74 75 76 77 133 79 80 81 82 100 84 31 86 87 88 100 90 91 92 93 94 95 96 97...
output:
1316 510 6401 1851 510 2657 1851 1222 2657 631 1222 750 631 2805 750 1640 2805 3835 1640 5370 3835 2964 5370 1968 2964 4101 1968 2279 4101 995 2279 938 995 182 938 1595 182 302 1595 2337 302 1581 2337 3804 1581 5137 3804 3730 5137 3471 3730 5622 3471 4666 5622 3699 4666 3505 3699 4614 3505 4189 4614...
result:
ok both subtasks are correct!
Test #11:
score: 5
Accepted
time: 23ms
memory: 31556kb
input:
400 100 88 82 9 2 90 1 83 32 32 79 8 79 63 67 85 82 50 63 69 2 7 91 21 90 69 3 39 78 66 83 96 53 24 65 56 63 90 54 35 55 94 22 76 12 54 55 5 49 91 73 8 19 64 54 39 23 13 27 34 4 81 52 13 11 36 45 3 50 82 81 42 50 75 15 99 70 29 26 70 66 34 15 42 83 16 19 19 12 76 1 68 49 7 17 64 37 98 34 99 37 34 64...
output:
14611 495 40001 577 495 483 577 659 483 1877 659 1559 1877 2234 1559 2859 2234 2766 2859 3944 2766 1834 3944 2923 1834 1376 2923 588 1376 884 588 1547 884 3546 1547 7854 3546 5317 7854 8992 5317 10672 8992 10041 10672 6381 10041 6889 6381 7496 6889 5596 7496 3982 5596 4756 3982 3179 4756 2889 3179 1...
result:
ok both subtasks are correct!
Test #12:
score: 5
Accepted
time: 10ms
memory: 30832kb
input:
301 20 8 1 1 1 1 1 1 17 1 9 1 5 1 1 1 1 13 1 9 1 18 1 1 16 1 15 5 19 1 8 11 10 1 1 1 1 18 4 1 1 1 1 16 1 1 1 12 10 1 1 1 14 11 13 1 1 1 1 1 1 10 1 1 1 1 1 1 19 14 1 1 1 5 1 1 1 1 13 1 18 1 1 4 1 1 1 1 1 1 1 1 1 1 16 16 10 1 14 18 1 1 1 7 1 1 1 1 6 9 1 13 1 1 1 2 1 1 1 1 1 1 10 1 1 1 17 1 10 10 1 12 ...
output:
4260 239 6021 5420 239 6008 5420 5603 6008 299 5603 5423 299 588 5423 2134 588 4624 2134 547 4624 2132 547 4012 2132 3796 4012 5015 3796 4152 5015 3524 4152 1367 3524 1888 1367 2209 1888 1918 2209 5209 1918 2665 5209 728 2665 2145 728 394 2145 3324 394 764 3324 948 764 1552 948 4597 1552 4133 4597 3...
result:
ok both subtasks are correct!
Test #13:
score: 5
Accepted
time: 70ms
memory: 35156kb
input:
300 300 215 159 263 206 201 183 286 56 142 10 231 214 34 54 263 250 169 208 239 148 104 22 244 17 74 68 184 52 2 30 42 83 222 106 25 152 37 225 213 213 69 273 91 221 207 48 166 28 221 50 46 64 10 254 207 109 206 144 270 291 195 197 253 235 141 186 102 68 52 24 38 6 181 44 256 200 77 233 285 163 223 ...
output:
32648 1094 90001 53 1094 2183 53 5950 2183 4458 5950 7764 4458 5669 7764 11016 5669 10292 11016 14769 10292 23575 14769 20009 23575 25349 20009 20038 25349 14804 20038 14329 14804 10311 14329 9553 10311 10841 9553 12967 10841 23844 12967 30523 23844 35646 30523 34333 35646 32469 34333 31677 32469 28...
result:
ok both subtasks are correct!
Test #14:
score: 5
Accepted
time: 78ms
memory: 38696kb
input:
201 400 1 1 1 1 1 152 1 1 1 1 1 1 1 33 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 300 154 1 1 147 1 1 1 383 186 1 1 90 256 1 1 1 1 1 1 1 63 1 1 1 1 208 1 1 1 1 31 1 1 1 1 1 1 1 127 1 1 29 216 397 393 1 1 1 1 1 1 279 1 1 1 1 55 1 1 215 249 1 1 1 1 1 1 172 1 1 1 1 1 1 1 1 1 1 1 1 349 1 331 1 1 1 1 1 1 1 34...
output:
63990 404 80401 9180 404 79224 9180 46275 79224 517 46275 23319 517 22972 23319 35645 22972 9740 35645 26962 9740 29412 26962 40471 29412 14975 40471 36621 14975 44512 36621 25443 44512 49706 25443 21025 49706 44273 21025 52573 44273 34104 52573 20988 34104 36842 20988 9138 36842 66757 9138 71724 66...
result:
ok both subtasks are correct!
Test #15:
score: 5
Accepted
time: 107ms
memory: 31456kb
input:
400 400 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
217 118784 160001 784 118784 160001 784 11722 160001 2922 11722 147572 2922 133420 147572 87336 133420 132109 87336 148555 132109 134930 148555 126916 134930 143716 126916 110130 143716 119755 110130 53963 119755 117163 53963 139563 117163 138000 139563 152588 138000 133788 152588 34188 133788 83080...
result:
ok both subtasks are correct!
Test #16:
score: 5
Accepted
time: 42ms
memory: 34476kb
input:
301 200 50 129 146 60 183 51 47 77 26 73 1 45 1 44 149 1 81 196 17 16 163 35 159 71 1 94 161 138 138 27 76 1 102 42 5 186 176 1 111 198 37 63 81 155 95 164 132 135 155 194 126 98 31 34 121 19 175 148 33 105 25 122 91 165 1 69 1 197 12 98 1 155 5 53 42 1 60 98 78 61 155 13 1 171 102 152 95 61 87 200 ...
output:
23506 532 60201 1539 532 3142 1539 5284 3142 7284 5284 14348 7284 16986 14348 14770 16986 18783 14770 15398 18783 22527 15398 21539 22527 19873 21539 30546 19873 35324 30546 34932 35324 33112 34932 39592 33112 44492 39592 53362 44492 59078 53362 57514 59078 54955 57514 51827 54955 43771 51827 39102 ...
result:
ok both subtasks are correct!
Test #17:
score: 5
Accepted
time: 78ms
memory: 42436kb
input:
201 400 1 1 1 1 1 1 1 1 1 1 1 1 1 263 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 246 1 1 1 1 1 1 1 1 1 1 1 1 1 1 107 1 1 1 1 1 1 1 1 57 1 1 1 1 1 1 1 224 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 90 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
77869 605 80401 41208 605 1106 41208 61913 1106 62868 61913 13423 62868 44857 13423 10966 44857 33797 10966 39885 33797 57586 39885 77530 57586 65318 77530 23480 65318 56741 23480 68282 56741 56250 68282 49385 56250 37309 49385 21602 37309 52 21602 10454 52 9875 10454 55098 9875 60039 55098 7386 600...
result:
ok both subtasks are correct!
Test #18:
score: 5
Accepted
time: 100ms
memory: 36764kb
input:
400 300 75 26 289 176 131 196 124 8 230 157 247 265 13 2 210 141 17 200 187 83 21 22 118 144 232 26 284 75 48 30 132 32 65 34 72 36 73 286 164 40 41 261 65 270 221 12 139 48 49 143 91 39 17 258 275 56 151 194 282 55 228 266 296 64 22 232 67 142 69 152 10 102 109 45 75 49 283 112 78 283 81 236 169 22...
output:
43105 1006 120001 5011 1006 5360 5011 1436 5360 2982 1436 3191 2982 5527 3191 3358 5527 870 3358 1132 870 252 1132 4741 252 6197 4741 9176 6197 4626 9176 2204 4626 435 2204 181 435 416 181 1454 416 5354 1454 6698 5354 4866 6698 4110 4866 9287 4110 20541 9287 18786 20541 16545 18786 13617 16545 12164...
result:
ok both subtasks are correct!
Test #19:
score: 5
Accepted
time: 124ms
memory: 45592kb
input:
333 399 1 1 1 1 1 1 1 28 1 1 1 1 1 1 161 1 17 1 1 1 1 262 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 43 1 1 1 1 1 70 1 1 1 142 1 1 1 1 1 1 1 1 1 1 1 1 70 1 1 1 1 1 1 278 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 245 1 1 1 1 1 1 33 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 106 1 1 1 1 268 1 1 1 172 1 1 1 1 1 312 1 286 1 1 1 1 ...
output:
114795 1003 132868 67603 1003 59111 67603 21459 59111 102611 21459 24897 102611 56339 24897 26114 56339 60012 26114 50770 60012 33748 50770 80008 33748 66465 80008 77425 66465 8521 77425 47309 8521 71391 47309 121384 71391 31944 121384 6742 31944 116235 6742 39918 116235 5425 39918 76937 5425 108084...
result:
ok both subtasks are correct!
Test #20:
score: 5
Accepted
time: 159ms
memory: 38848kb
input:
400 400 100 35 353 385 317 228 7 148 113 165 11 306 209 89 21 166 17 2 19 249 27 305 377 22 3 353 38 28 29 96 191 32 33 309 35 308 100 176 152 40 176 42 43 86 45 46 96 48 396 381 218 246 53 54 334 159 243 360 294 60 33 62 185 64 65 66 191 121 351 107 10 343 367 74 75 201 77 247 79 134 304 92 42 126 ...
output:
55816 1074 160001 1228 1074 3159 1228 7627 3159 9536 7627 6151 9536 9169 6151 21913 9169 31428 21913 50569 31428 56545 50569 87872 56545 106820 87872 112497 106820 122969 112497 117407 122969 109535 117407 102121 109535 105193 102121 111788 105193 102918 111788 118325 102918 122568 118325 120184 122...
result:
ok both subtasks are correct!