Submission #255678

#	Time	Username	Problem	Language	Result	Execution time	Memory
255678		sonvip9	Trobojnica (COCI19_trobojnica)	C++14	60 / 110	8 ms	9356 KiB

trobojnica

#include <bits/stdc++.h>
#define fr(i,x,y) for(int i=x;i<=y;i++)
#define frd(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
#define maxn 300100
#define Bit(x,i) ((x>>i)&1)
#define Turnoff(t,k) (t^(1<<(k)))
using namespace std;
int n,m = 0;
int cnt[3],d[1010][1010],v[1010],res = 0,check = 0;
string s;
void inp()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("tasktrobojnica.inp","r",stdin);
    //freopen("tasktrobojnica.out","w",stdout);
    cin>>n>>s;
    fr(i,0,n-1)  
    {
        cnt[s[i]-'1']++;
        if (i == n-1) d[n][1] = d[1][n] = s[i] - '1';
        else d[i+1][i+2] = d[i+2][i+1] = s[i] - '1';
    }
}
void sub()
{
    fr(i,0,2) if (cnt[i] == 0) check++;
    if ((check > 1) || (cnt[0] % 2 != n % 2) || (cnt[1] % 2 != n % 2) || (cnt[2] % 2 != n % 2))
	{
        cout<<"NE";
        return;
    }
    cout<<"DA\n";
    fr(i,1,n) v[i] = i; 
    m = n;
    while (res + 1 <= n - 3)
    {
        bool ok = false;
        res++;
        fr(i,1,m-2)
        {
            if (d[v[i]][v[i+1]] == d[v[i+1]][v[i+2]]) continue;
            int dem[3];
            fr(j,0,2) dem[j] = cnt[j]; 
            dem[d[v[i]][v[i+1]]]--; dem[d[v[i+1]][v[i+2]]]--; dem[3-d[v[i]][v[i+1]]-d[v[i+1]][v[i+2]]]++;
            check = 0;
            fr(i,0,2) if (dem[i] == 0) check++;
            if ((check <= 1) && (dem[0] % 2 == (m-1) % 2) && (dem[1] % 2 == (m-1) % 2) && (dem[2] % 2 == (m-1) % 2))
            {
                d[v[i]][v[i+2]] = d[v[i+2]][v[i]] = 3-d[v[i]][v[i+1]]-d[v[i+1]][v[i+2]];
                cout<<v[i]<<" "<<v[i+2]<<" "<<d[v[i]][v[i+2]]+1<<"\n";
                fr(j,0,2) cnt[j] = dem[j];
                fr(j,i+1,m-1) v[j] = v[j+1];
                m--;
                ok = true;
                break;
            }
        }
        if (!ok)
        {
            if (d[v[m-1]][v[m]] == d[v[m]][v[1]]) continue;
            int dem[3];
            fr(j,0,2) dem[j] = cnt[j]; 
            dem[d[v[m-1]][v[m]]]--; dem[d[v[m]][v[1]]]--; dem[3-d[v[m-1]][v[m]]-d[v[m]][v[1]]]++;
            check = 0;
            fr(i,0,2) if (dem[i] == 0) check++;
            if ((check <= 1) && (dem[0] % 2 == (m-1) % 2) && (dem[1] % 2 == (m-1) % 2) && (dem[2] % 2 == (m-1) % 2))
            {
                d[v[m-1]][v[1]] = d[v[1]][v[m-1]] = 3-d[v[m-1]][v[m]]-d[v[m]][v[1]];
                cout<<v[m-1]<<" "<<v[1]<<" "<<d[v[m-1]][v[1]]+1<<"\n";
                fr(j,0,2) cnt[j] = dem[j];
                m--;
                ok = true;
            }
        }
        if (!ok)
        {
            if (d[v[m]][v[1]] == d[v[1]][v[2]]) continue;
            int dem[3];
            fr(j,0,2) dem[j] = cnt[j]; 
            dem[d[v[m]][v[1]]]--; dem[d[v[1]][v[2]]]--; dem[3-d[v[m]][v[1]]-d[v[1]][v[2]]]++;
            check = 0;
            fr(i,0,2) if (dem[i] == 0) check++;
            if ((check <= 1) && (dem[0] % 2 == (m-1) % 2) && (dem[1] % 2 == (m-1) % 2) && (dem[2] % 2 == (m-1) % 2))
            {
                d[v[m]][v[2]] = d[v[2]][v[m]] = 3-d[v[m]][v[1]]-d[v[1]][v[2]];
                cout<<v[m]<<" "<<v[2]<<" "<<d[v[m]][v[2]]+1<<"\n";
                fr(j,0,2) cnt[j] = dem[j];
                fr(j,1,m-1) v[j] = v[j+1]; 
                m--;
                ok = true;
            }
        }
    }
}
int main()
{
    inp();
    sub();
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50