oj.uz

Submission #257047

# Submission time Handle Problem Language Result Execution time Memory
257047 2020-08-03T14:53:49 Z sonvip9 Trobojnica (COCI19_trobojnica) C++14
20 / 110
 2000 ms 8320 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair <int,int>
#define pl pair <ll,ll>
#define fr(i,x,y) for (int i=x;i<=y;i++)
#define ft(i,x,y) for (int i=y;i>=x;i--)
#define N 100005
using namespace std ;
int n,color[1002][1002],first_color[1002][1002],dem_mau[N][3];
string s;
void inp()
{
    //freopen("task2.inp","r",stdin) ;
    //freopen("task2.out","w",stdout);
    cin>>n>>s;
}
bool hs(int u,int v)
{
    if (u>v) swap(u,v);
    if (u==1 and v==n) return true ;
    return false;
}
int tong_color(int st,int ed,int col){
    return dem_mau[n][col] - (dem_mau[n][col]-dem_mau[ed-3][col]) - (dem_mau[st][col]-dem_mau[1][col]);
}
bool check()
{
//    fr(i,1,n)
//    {
//        fr(j,i+1,n)
//           fr(k,j+1,n)
//            {
//                if (color[i][j]!=0 and color[i][k]!=0 and color[k][j]!=0)
//                    if (color[i][j]==color[i][k] or color[i][j]==color[j][k] or color[k][j]==color[i][k]) return false ;
//            }
//    }
    int dem = 0 ;
    fr(i,1,n)
    {
        fr(j,i+2,n)
        {
            if (hs(i,j)) continue ;
            if (color[i][j]!=0) dem++;
        }
    }
    if (dem!=n-3) return false ;
    return true ;
}
bool checking_chanle(int a,int b,int c){
   // cout<<a<<" "<<b<<" "<<c<<endl;
    a = max(a,0);
    b = max(b,0);
    c = max(c,0);
    int tong = a+b+c ;
    int r = tong%2;
    if((a==0 and b==0) or (a==0 and c==0) or (b==0 and c==0)) return false ;
    if (a%2!=r or b%2!=r or c%2!=r) return false ;
    return true ;
}
bool ad = true ;
void duyet(int st,int ed)
{
    if (st>ed) swap(st,ed);
    if (ed-st==2)
    {
        if (check())
        {
            cout<<"DA"<<"\n";
            fr(i,1,n)
            {
                fr(j,i+2,n)
                {
                    if (color[i][j]!=0)
                    {
                        if (hs(i,j)) continue ;
                        cout<<i<<" "<<j<<" "<<color[i][j]<<"\n";
                    }
                }
            }
            exit(0);
        }
        return ;
    }
    fr(i,st+1,ed-1)
    {
        fr(now_color,1,3)
        {
            if (now_color!=color[st][ed])
            {
                int dem_ed_phai[4],dem_ed_trai[4],dem_st_phai[4],dem_st_trai[4];
                fr(j,1,3){
                   //if (ed!=n)
                   dem_ed_trai[j] = dem_mau[ed-1][j]-dem_mau[i-1][j];
                   //else
                      //dem_ed_trai[j] = dem_mau[ed][j] - dem_mau[i-1][j];

                   dem_ed_phai[j] = dem_mau[n][j] - dem_ed_trai[j] ;
                   dem_st_trai[j] = dem_mau[i-1][j]-dem_mau[st-1][j] ;
                   dem_st_phai[j] = dem_mau[n][j] - dem_st_trai[j];
                }
                bool ok1 = true , ok2 = true  ;
                if (color[st][i]==0) {
                        color[st][i] = color[i][st] = 6 - now_color - color[st][ed];
                        dem_st_phai[color[st][i]]++;
                        dem_st_trai[color[st][i]]++;
                        ok1 = false ;
                }
                if (color[ed][i]==0){
                    color[ed][i] = color[i][ed] = now_color ;
                    dem_ed_phai[color[ed][i]]++;
                    dem_ed_trai[color[ed][i]]++;
                    ok2 = false ;
                }
                //cout<<ed-1<<" "<<dem_mau[6][1]<<" "<<dem_mau[i-1][1]<<endl;
//                if (st==1 and ed==9 and i==7 and color[9][7]==3){
//                    cout<<dem_mau[ed-1][1]<<" "<<dem_mau[i-1][1]<<" "<<color[ed][i]<<endl;
//                    cout<<"DINH: "<<st<<" "<<ed<<" "<<i<<endl ;
//                    cout<<"MAU: "<<color[st][ed]<<" "<<color[st][i]<<" "<<color[ed][i]<<endl;
//                    cout<<"PHAIst: "<<dem_st_phai[1]<<" "<<dem_st_phai[2]<<" "<<dem_st_phai[3]<<endl;
//                    cout<<"TRAIst: "<<" "<<dem_st_trai[1]<<" "<<dem_st_trai[2]<<" "<<dem_st_trai[3]<<endl;
//                    cout<<endl;
//                    cout<<"PHAIed: "<<dem_ed_phai[1]<<" "<<dem_ed_phai[2]<<" "<<dem_ed_phai[3]<<endl;
//                    cout<<"TRAIed: "<<dem_ed_trai[1]<<" "<<dem_ed_trai[2]<<" "<<dem_ed_trai[3]<<endl;
//                }
                if (checking_chanle(dem_ed_phai[1],dem_ed_phai[2],dem_ed_phai[3]))
                    if (checking_chanle(dem_ed_trai[1],dem_ed_trai[2],dem_ed_trai[3]))
                        ok2 = true ;
                if (checking_chanle(dem_st_phai[1],dem_st_phai[2],dem_st_phai[3]))
                     if (checking_chanle(dem_st_trai[1],dem_st_trai[2],dem_st_trai[3]))
                       ok1 = true ;
                //cout<<ok1<<" "<<ok2<<endl;
                //cout<<"----------------"<<endl;
                if (ok1 and ok2)
                {

                     //cout<<"PASSED !!"<<endl;
                     duyet(st,i);
                     duyet(ed,i);
                }
                color[i][st] = color[st][i] = first_color[st][i];
                color[i][ed] = color[ed][i] = first_color[ed][i];
            }
        }
    }
}
void sub1()
{
    fr(i,0,n-1)
    {
        if (i!=n-1)
        {
            color[i+1][i+2] = color[i+2][i+1] = s[i]-'0';
        }
        else color[1][n] = color[n][1] = s[i]-'0';
    }
    s=" "+s;
    fr(i,1,n){
       fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
       dem_mau[i][s[i]-'0']++;
    }
    if (!checking_chanle(dem_mau[n][1],dem_mau[n][2],dem_mau[n][3])){
        cout<<"NE";
        exit(0);
    }
    fr(i,1,n)
      fr(j,1,n)
         first_color[i][j] = color[i][j];
    duyet(n,1);
    cout<<"NE";
}
int main()
{
    inp();
    sub1();
}

Compilation message

trobojnica.cpp: In function 'void duyet(int, int)':
trobojnica.cpp:96:52: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
                    dem_ed_trai[j] = dem_mau[ed-1][j]-dem_mau[i-1][j];
                                     ~~~~~~~~~~~~~~~^
trobojnica.cpp:8:33: note: within this loop
 #define fr(i,x,y) for (int i=x;i<=y;i++)
trobojnica.cpp:94:20:
                 fr(j,1,3){
                    ~~~~~         
trobojnica.cpp:94:17: note: in expansion of macro 'fr'
                 fr(j,1,3){
                 ^~
trobojnica.cpp: In function 'void sub1()':
trobojnica.cpp:161:48: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
        fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
                                  ~~~~~~~~~~~~~~^
trobojnica.cpp:8:33: note: within this loop
 #define fr(i,x,y) for (int i=x;i<=y;i++)
trobojnica.cpp:161:11:
        fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
           ~~~~~                  
trobojnica.cpp:161:8: note: in expansion of macro 'fr'
        fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
        ^~
trobojnica.cpp:161:48: warning: array subscript is above array bounds [-Warray-bounds]
        fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
                                  ~~~~~~~~~~~~~~^
trobojnica.cpp:161:30: warning: array subscript is above array bounds [-Warray-bounds]
        fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
                  ~~~~~~~~~~~~^
trobojnica.cpp:164:25: warning: array subscript is above array bounds [-Warray-bounds]
     if (!checking_chanle(dem_mau[n][1],dem_mau[n][2],dem_mau[n][3])){
          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 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
0.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 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 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 3 ms 4224 KB Output is correct
13 Correct 25 ms 8320 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Execution timed out 2092 ms 8312 KB Time limit exceeded
17 Halted 0 ms 0 KB -

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 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 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 3 ms 4224 KB Output is correct
13 Correct 25 ms 8320 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Execution timed out 2092 ms 8312 KB Time limit exceeded
17 Halted 0 ms 0 KB -