QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126523 | #6668. Trokuti | angry_face | 0 | 21ms | 3888kb | C++14 | 3.9kb | 2023-07-18 16:05:21 | 2023-07-18 16:05:25 |
Judging History
answer
# include <iostream>
# include <cstdio>
# include <vector>
# include <ctime>
# include <algorithm>
using namespace std ;
int n = 100 , a[205][205] , num[205][205] ;
int p[205] , st[205] ;
int cnt , x1 , x2 , x3 , cntq , q[205] ;
int f[205][205][205];
int ans ;
vector < int > vec ;
int query( int x , int y , int z )
{
cnt++ ;
printf("? %d %d %d\n" , x , y , z) ;
fflush( stdout ) ;
int t ;
scanf("%d" , &t) ;
return t ;
}
int solve(int u,int v,int w)
{
x1 = ( u - v + w ) / 2 ;
x2 = v - x1 ;
x3 = w - x1 ;
}
int main()
{
srand( time( 0 ) ) ;
// for ( int i = 1 ; i <= n ; i++ )
// for ( int j = i + 1 ; j <= n ; j++ ) a[i][j] = a[j][i] = rand() % 2 ;
for ( int i = 1 ; i <= n ; i++ ) p[i] = i ;
random_shuffle( p + 1 , p + n + 1 ) ;
for ( int i = 1 ; i <= 6 ; i++ )
for ( int j = i + 1 ; j <= 6 ; j++ )
for ( int k = j + 1 ; k <= 6 ; k++ )
{
if ( vec.size() ) continue ;
ans = query( p[i] , p[j] , p[k] ) ;
f[i][j][k]=ans;
if ( ! ans )
{
//vec.push_back( p[i] ) , vec.push_back( p[j] ) , vec.push_back( p[k] ) ;
//st[p[i]] = st[p[j]] = st[p[k]] = 1;
}
else if ( ans == 3 )
{
//vec.push_back( p[i] ) , vec.push_back( p[j] ) , vec.push_back( p[k] ) ;
//st[p[i]] = st[p[j]] = st[p[k]] = 1;
//num[p[i]][p[j]] = num[p[j]][p[i]] = num[p[i]][p[k]] = num[p[k]][p[i]] = num[p[j]][p[k]] = num[p[k]][p[j]] = 1 ;
}
}
for(int i=1;i<=6;i++) st[p[i]]=1;
for(int i=1;i<=6;i++) vec.push_back(p[i]);
for(int s=0;s<(1<<15);s++)
{
int cur=0;
for(int j=1;j<=6;j++)
{
for(int k=j+1;k<=6;k++)
{
if((s&(1<<cur))==0) num[p[j]][p[k]]=num[p[k]][p[j]]=0;
else num[p[j]][p[k]]=num[p[k]][p[j]]=1;
cur++;
}
}
bool flag=true;
for(int i=1;i<=6;i++)
{
for(int j=i+1;j<=6;j++)
{
for(int k=j+1;k<=6;k++)
{
int now=0;
if(num[p[i]][p[j]]==1) now++;
if(num[p[k]][p[j]]==1) now++;
if(num[p[i]][p[k]]==1) now++;
if(now!=f[i][j][k]) flag=false;
}
}
}
if(flag==true) break;
}
for ( int i = 1 ; i <= n ; i++ )
{
if ( st[p[i]] ) continue ;
cntq =0 ;
for ( auto j : vec ) q[++ cntq] = j ;
random_shuffle( q + 1 , q + cntq + 1 ) ;
int tnum = 1 ;
while ( tnum + 2 <= cntq )
{
int ansb = query( p[i] , q[tnum] , q[tnum + 1] ) - num[q[tnum]][q[tnum + 1]] ;
if ( ansb == 0 || ansb == 2 )
{
num[p[i]][q[tnum]] = num[q[tnum]][p[i]] = num[p[i]][q[tnum + 1]] = num[q[tnum + 1]][p[i]] = ansb / 2 ;
tnum += 2 ;
continue ;
}
int nbc = query( p[i] , q[tnum + 1] , q[tnum + 2] ) - num[q[tnum + 1]][q[tnum + 2]] ;
if ( nbc == 0 || nbc == 2 )
{
num[p[i]][q[tnum + 1]] = num[q[tnum + 1]][p[i]] = num[p[i]][q[tnum + 2]] = num[q[tnum + 2]][p[i]] = nbc / 2 ;
num[p[i]][q[tnum]] = num[q[tnum]][p[i]] = ansb - num[p[i]][q[tnum + 1]] ;
tnum += 3 ;
continue ;
}
int ansc = query( p[i] , q[tnum] , q[tnum + 2] ) - num[q[tnum]][q[tnum + 2]] ;
solve( ansb , nbc , ansc ) ;
num[p[i]][q[tnum]] = num[q[tnum]][p[i]] = x1 ;
num[p[i]][q[tnum + 1]] = num[q[tnum + 1]][p[i]] = x2 ;
num[p[i]][q[tnum + 2]] = num[q[tnum + 2]][p[i]] = x3 ;
tnum += 3 ;
}
if ( tnum <= cntq )
{
num[p[i]][q[tnum]] = num[q[tnum]][p[i]] = query( p[i] , q[tnum - 1] , q[tnum] ) - num[p[i]][q[tnum - 1]] - num[q[tnum - 1]][q[tnum]] ;
}
if ( tnum + 1 <= cntq )
{
num[p[i]][q[tnum + 1]] = num[q[tnum + 1]][p[i]] = query( p[i] , q[tnum - 1] , q[tnum + 1] ) - num[p[i]][q[tnum - 1]] - num[q[tnum - 1]][q[tnum + 1]] ;
}
vec.push_back( p[i] ) ;
st[p[i]] = true ;
}
// for ( int i = 1 ; i <= n ; i++ )
// for ( int j = i + 1 ; j <= n ; j++ )
// {
// if ( num[i][j] != a[i][j] )
// {
// printf("GG:%d %d\n" , i , j) ;
// }
// }
puts("!") ;
for ( int i = 1 ; i <= n ; i++ )
{
for ( int j = 1 ; j <= n ; j++ ) printf("%d" , num[i][j]) ;
puts("") ;
}
fflush( stdout ) ;
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
? 91 54 21 ? 91 54 52 ? 91 54 10 ? 91 54 34 ? 91 21 52 ? 91 21 10 ? 91 21 34 ? 91 52 10 ? 91 52 34 ? 91 10 34 ? 54 21 52 ? 54 21 10 ? 54 21 34 ? 54 52 10 ? 54 52 34 ? 54 10 34 ? 21 52 10 ? 21 52 34 ? 21 10 34 ? 52 10 34 ? 8 54 91 ? 8 52 21 ? 8 21 34 ? 8 21 10 ? 7 91 52 ? 7 8 34 ? 7 54 10 ? 7 10 21 ?...
result:
points 1.0 points 1.0 correct 2558 queries
Test #2:
score: 100
Accepted
time: 21ms
memory: 3752kb
input:
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
output:
? 77 5 18 ? 77 5 95 ? 77 5 62 ? 77 5 47 ? 77 18 95 ? 77 18 62 ? 77 18 47 ? 77 95 62 ? 77 95 47 ? 77 62 47 ? 5 18 95 ? 5 18 62 ? 5 18 47 ? 5 95 62 ? 5 95 47 ? 5 62 47 ? 18 95 62 ? 18 95 47 ? 18 62 47 ? 95 62 47 ? 98 5 62 ? 98 77 47 ? 98 47 95 ? 98 47 18 ? 28 47 77 ? 28 5 98 ? 28 62 95 ? 28 95 18 ? 74...
result:
points 1.0 points 1.0 correct 2558 queries
Test #3:
score: 0
Runtime Error
input:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
? 77 5 18 ? 77 5 95 ? 77 5 62 ? 77 5 47 ? 77 18 95 ? 77 18 62 ? 77 18 47 ? 77 95 62 ? 77 95 47 ? 77 62 47 ? 5 18 95 ? 5 18 62 ? 5 18 47 ? 5 95 62 ? 5 95 47 ? 5 62 47 ? 18 95 62 ? 18 95 47 ? 18 62 47 ? 95 62 47 ? 98 5 62 ? 98 77 47 ? 98 47 95 ? 98 47 18 ? 28 47 77 ? 28 5 98 ? 28 62 95 ? 28 95 18 ? 74...