QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#141448	#5280. Depot Rearrangement	PCTprobability^#	95	159ms	45592kb	C++14	8.6kb	2023-08-17 13:39:42	2024-07-04 01:46:38

Judging History

你现在查看的是最新测评结果

[2024-07-04 01:46:38]
评测

测评结果：95
用时：159ms
内存：45592kb

查看

[2023-08-17 13:39:42]
提交

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];
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<ll> c(m);
    for(int j=0;j<m;j++) c[a[i][j]]++;
    for(int j=0;j<m;j++){
      if(c[j]==0){
        p[x]={i,j};
        pf[i].pb(x);
        ps[j].pb(x);
        x++;
        cnt++;
      }
      else{
        for(int k=0;k<c[j]-1;k++){
          q[y]={i,j};
          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]==0&&c[k]>=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);
          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);
          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);
          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);
          t.merge(id[j]+x,id[j+1]+x);
          sz--;
        }
      }
    }
  }
  cout<<cnt+sz<<endl;
}

源文件, 语言: C++14

详细

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:

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:

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:

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:

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:

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:

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:

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!