oj.uz

Submission #341104

# Submission time Handle Problem Language Result Execution time Memory
341104 2020-12-29T02:23:03 Z rrrr10000 JOIRIS (JOI16_joiris) C++14
30 / 100
 2 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dame(a) {out(a);return 0;}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
vp ans;
void tate(int i){
    ans.pb(1,i+1);
}
void yoko(int i){
    ans.pb(2,i+1);
}
int main(){
    ll n,k;cin>>n>>k;
    vi v(n);rep(i,n)cin>>v[i];
    vi dif(n+1);
    dif[0]=inf;dif[n]=inf;
    rep(i,n-1)dif[i+1]=v[i+1]-v[i];
    vi sum(k);
    rep(i,n+1)sum[i%k]+=dif[i];
    rep(i,k)if(sum[i]%__gcd(n,k)!=0&&sum[i]<1001001001)dame(-1);
    assert(k==2);
    ll ma=0;
    rep(i,n)chmax(ma,v[i]);
    rep(i,n)while(v[i]<ma){
        tate(i);
        v[i]+=k;
    }
    rep(i,n)v[i]-=ma;
    auto check=[&](){
        bool done=true;
        rep(i,n)if(v[i])done=false;
        if(done){
            out(ans.size());for(auto x:ans)cout<<x.fi<<' '<<x.se<<endl;
        }
        return done;
    };
    if(check())return 0;
    ll cnt=0;
    rep(i,n)if(v[i])cnt++;
    if(cnt%2==1&&n%2==0)dame(-1);
    if(cnt%2==0&&n%2==1){
        rep(i,n){
            if(v[i]==0)tate(i);
            v[i]=1-v[i];
        }
    }
    ll c=0;
    for(int i=n-1;i>=0;i--){
        if(v[i]==0)c++;
        else{
            if(c%2){
                yoko(i);
                rep(j,n)if(j!=i&&j!=i+1)tate(j);
                tate(i+1);
                v[i]=0;v[i+1]=1;
                c=1;
            }
            else c=0;
        }
    }
    rep(i,n-1)if(v[i]==0){
        assert(v[i+1]==0);
        yoko(i);
        v[i]=1;v[i+1]=1;
    }
    assert(v[n-1]==1);
    // assert(ans.size()<=10000);
    out(ans.size());
    for(auto x:ans)cout<<x.fi<<' '<<x.se<<endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 2 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 2 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
36 Halted 0 ms 0 KB -