oj.uz

Submission #255678

# Submission time Handle Problem Language Result Execution time Memory
255678 2020-08-01T14:17:42 Z sonvip9 Trobojnica (COCI19_trobojnica) C++14
60 / 110
 8 ms 9356 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 2 ms 4224 KB Output is correct
13 Correct 3 ms 4352 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 3 ms 4352 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 3 ms 4352 KB Output is correct
19 Correct 2 ms 4224 KB Output is correct
20 Correct 3 ms 4352 KB Output is correct

Subtask #3
0.0 / 50.0

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