제출 #1182999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182999		vnedu	JOIRIS (JOI16_joiris)	C++20	100 / 100	1 ms	584 KiB

joiris

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int lim = 50;
const int N = 55;

int n,k,a[N],d[N];
vector<int> cc[N];
vector<ii> history;

void print()
{
    for (int i=1; i<=n; ++i) cout<<a[i]<<' ';
    cout<<'\n';
}
void ver(int x)
{
    history.pb(make_pair(1,x));
}
void hor(int x)
{
    history.pb(make_pair(2,x));
}
void addSelf(int &x, int val)
{
    x+=val;
    if (x>=k) x-=k;
    else if (x<0) x+=k;
}
int returnSelf(int x, int val)
{
    x+=val;
    if (x>=k) x-=k;
    else if (x<0) x+=k;
    return x;
}
void relax()
{
    int mn=INT_MAX;
    for (int i=1; i<=n; ++i) minimize(mn,a[i]);
    for (int i=1; i<=n; ++i) a[i]-=mn;
}
void add(int x, int val)
{
    for (int i=1; i<=n; ++i)
    {
        if (x<=i && i<=x+k-1) continue;
        ver(i); a[i]+=k;
        ver(i); a[i]+=k;
    }
    for (int i=1; i<=val; ++i)
    {
        hor(x);
    }
    for (int j=x; j<=x+k-1; ++j) a[j]+=val;
    for (int i=1; i<=n; ++i)
    {
        a[i]-=val;
        while (a[i]<2*k)
        {
            ver(i);
            a[i]+=k;
        }
    }
    relax();
}

void solve()
{
    cin>>n>>k;
    for (int i=1; i<=n; ++i)
    {
        cin>>a[i];
        while (a[i]<k*lim)
        {
            ver(i);
            a[i]+=k;
        }
    }
    relax();
//    print();
//    for (int i=1; i<=n; ++i) cout<<a[i]<<' ';
//    cout<<'\n';
    for (int i=1; i<=n; ++i) d[i]=returnSelf(a[i],-a[i-1]);
//    for (int i=1; i<=n; ++i) cout<<d[i]<<' ';
//    return;
    set<int> spec;
    if (k+1<=n) spec.insert((k+1)%k);
    if (n+1-k>=2) spec.insert((n+1-k)%k);

    for (int i=2; i<=n; ++i) cc[i%k].pb(i);
    for (int j=0; j<k; ++j) if(!spec.count(j))
    {
//        cout<<j<<'\n';
        int sum=0;
        for (int x : cc[j]) sum=(sum+d[x])%k;
        if (sum!=0) return void(cout<<-1);
        int sz=(int)cc[j].size();
        for (int i=0; i<sz-1; ++i)
        {
            int x=cc[j][i];
            int val=returnSelf(k-d[x],0);
//            cout<<x<<' '<<val<<' '<<k<<' '<<d[x]<<'\n';
            addSelf(d[x+k],-val);
            d[x]=0;
//            sum=0;
//            for (int x : cc[j]) addSelf(sum,d[x]);
//            if (sum!=0) return void(cout<<1/0);
//            if (cc[j][i+1]!=x+k) return void(cout<<1/0);
//            sum=0;
//            for (int p=i+1; p<sz; ++p) addSelf(sum,d[cc[j][p]]);
//            if (sum!=0) return void(cout<<1/0);
            add(x,val);
        }
//        for (int x : cc[j]) if (d[x]!=0) return void(cout<<1/0);
//        sum=0;
//        for (int x : cc[j]) addSelf(sum,d[x]);
//        if (sum!=0) return void(cout<<1/0);
//        if(sz>1 && returnSelf(0,d[cc[j][sz-1]])!=0) return void(cout<<1/0);
    }
//    for (int j=0; j<k; ++j)
//    {
//        for (int x : cc[j]) cout<<x<<' ';
//        cout<<'\n';
//    }
//    return;
    for (int j : spec)
    {
        int sz=(int)cc[j].size();
        if (n+1-k>=2 && (n+1-k)%k==j%k)
        {
            for (int i=0; i<sz-1; ++i)
            {
                int x=cc[j][i];
                int val=returnSelf(k-d[x],0);
                addSelf(d[x+k],-val);
                add(x,val);
            }
            int x=cc[j][sz-1];
            int val=returnSelf(k-d[x],0);
//            cout<<x<<' '<<val<<'\n';
            add(x,val);
        }
        else
        {
            for (int i=sz-1; i>=1; --i)
            {
                int x=cc[j][i];
                int val=d[x];
                addSelf(d[x-k],val);
                add(x-k,val);
            }
            add(1,d[cc[j][0]]);
//            cout<<1<<' '<<cc[j][0]<<'\n';
        }
    }
//    for (int i=1; i<n; ++i) if (a[i]!=a[i+1]) return void(cout<<1/0);
//    for (int i=1; i<n; ++i) if (a[i]!=a[i+1]) return void(cout<<"WTF");
//    for (int i=1; i<=n; ++i) cout<<a[i]<<' ';
//    return;
    if ((int)history.size()>10000) return void(cout<<1/0);
    cout<<(int)history.size()<<'\n';
    for (ii cm : history) cout<<cm.fi<<' '<<cm.se<<'\n';
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joiris.cpp: In function 'void solve()':
joiris.cpp:177:55: warning: division by zero [-Wdiv-by-zero]
  177 |     if ((int)history.size()>10000) return void(cout<<1/0);
      |                                                      ~^~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55