#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_benphai[4],dem_bentrai[4];
fr(j,1,3){
dem_benphai[j] = dem_mau[i-1][j]-dem_mau[st-1][j];
dem_bentrai[j] = dem_mau[n][j] - dem_benphai[j] ;
}
if (color[st][i]==0) {
color[st][i] = color[i][st] = 6 - now_color - color[st][ed];
dem_benphai[color[st][i]]++;
dem_bentrai[color[st][i]]++;
}
if (color[ed][i]==0){
color[ed][i] = color[i][ed] = now_color ;
dem_benphai[color[ed][i]]++;
dem_bentrai[color[ed][i]]++;
}
//if (checking_chanle(dem_benphai[1],dem_benphai[2],dem_benphai[3]) or i==st+1)
// if (checking_chanle(dem_bentrai[1],dem_bentrai[2],dem_bentrai[3]) or i==st+1)
{
//cout<<"OK"<<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']++;
}
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:95:51: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
dem_benphai[j] = dem_mau[i-1][j]-dem_mau[st-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:134: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:134:11:
fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
~~~~~
trobojnica.cpp:134:8: note: in expansion of macro 'fr'
fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
^~
trobojnica.cpp:134: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:134:30: warning: array subscript is above array bounds [-Warray-bounds]
fr(j,1,3) dem_mau[i][j] = dem_mau[i-1][j];
~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
18 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 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 |
10 ms |
476 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
18 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 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 |
10 ms |
476 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Execution timed out |
2096 ms |
8320 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
18 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 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 |
10 ms |
476 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Execution timed out |
2096 ms |
8320 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
