QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#857531#8871. Interactive Reconstructiongs22059test#AC ✓122ms8960kbC++238.3kb2025-01-15 20:17:042025-01-15 20:17:04

Judging History

This is the latest submission verdict.

  • [2025-01-15 20:17:04]
  • Judged
  • Verdict: AC
  • Time: 122ms
  • Memory: 8960kb
  • [2025-01-15 20:17:04]
  • Submitted

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3") // optimization
//#pragma GCC optimize("Ofast") // optimization
//#pragma GCC optimize("unroll-loops") // optimization
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define i32 signed
#define int long long // CP
#define i64 long long
#define endl '\n'
#define elif else if
#define fi first
#define se second
#define pb push_back
#define p32 pair<i32,i32>
#define p64 pair<i64,i64>
#define f2(i,x) for((i)=0;(i)<(x);(i)++)
#define f2b(i,x) for((i)=(x)-1;(i)>=0;(i)--)
#define f3(i,f,t) for((i)=(f);(i)<(t);(i)++)
#define fall(x) (x).begin(), (x).end()
#define sort1(x) sort(fall(x))
#define rev(x) reverse(fall(x))
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fl fflush(stdout)
#define nl cout<<endl;fflush(stdout)
i64 gcd(i64 a, i64 b){if(a<b){a=a^b;b=a^b;a=a^b;} return b==0?a:gcd(b,a%b);}
i64 lcm(i64 a, i64 b){return a/gcd(a,b)*b;}
i64 expm(i64 a, i64 b, i64 m){i64 r=1;while(b){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}return r%m;}
i64 expm(i64 a, i64 b){i64 r=1,m=1e9+7;while(b){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}return r%m;}
i64 minv(i64 a, i64 m){return expm(a,m-2,m);}
i64 ncrm(i64 n, i64 r, i64 m){i64 i,j,k; i64 out=1; f3(i,1,n+1){out*=i;out%=m;}f3(i,1,r+1){out*=minv(i,m);out%=m;}f3(i,1,n-r+1){out*=minv(i,m);out%=m;}return out%m;}
// int n,m,k,a[300010],b[300010],c[300010];
double dist(p64 a,p64 b){
    return sqrt((double)(a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se));
}
void probA(){
    int i,j,l;
}void probC(){
    int i,j,l;
}void probD(){
    // int i,j,l;
    // int n,q; cin>>n>>q;
    // vector<int>a(n),b(n),c(n); for(int i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i];
    // while(q--){
    //
    // }
}void probF(){
    int i,j,l;
}

const int N = 3e5 + 9;

const double inf = 1e100;
const double eps = 1e-10;
const double PI = acos((double)-1.0);
int sign(double x) { return (x > eps) - (x < -eps); }
struct PT {
    double x, y;
    PT() { x = 0, y = 0; }
    PT(double x, double y) : x(x), y(y) {}
    PT(const PT &p) : x(p.x), y(p.y)    {}
    PT operator + (const PT &a) const { return PT(x + a.x, y + a.y); }
    PT operator - (const PT &a) const { return PT(x - a.x, y - a.y); }
    PT operator * (const double a) const { return PT(x * a, y * a); }
    friend PT operator * (const double &a, const PT &b) { return PT(a * b.x, a * b.y); }
    PT operator / (const double a) const { return PT(x / a, y / a); }
    bool operator == (PT a) const { return sign(a.x - x) == 0 && sign(a.y - y) == 0; }
    bool operator != (PT a) const { return !(*this == a); }
    bool operator < (PT a) const { return sign(a.x - x) == 0 ? y < a.y : x < a.x; }
    bool operator > (PT a) const { return sign(a.x - x) == 0 ? y > a.y : x > a.x; }
    double norm() { return sqrt(x * x + y * y); }
    double norm2() { return x * x + y * y; }
    PT perp() { return PT(-y, x); }
    double arg() { return atan2(y, x); }
    PT truncate(double r) { // returns a vector with norm r and having same direction
        double k = norm();
        if (!sign(k)) return *this;
        r /= k;
        return PT(x * r, y * r);
    }
};

istream &operator >> (istream &in, PT &p) { return in >> p.x >> p.y; }
ostream &operator << (ostream &out, PT &p) { return out << "(" << p.x << "," << p.y << ")"; }
inline double dot(PT a, PT b) { return a.x * b.x + a.y * b.y; }
inline double dist2(PT a, PT b) { return dot(a - b, a - b); }
inline double dist(PT a, PT b) { return sqrt(dot(a - b, a - b)); }
inline double cross(PT a, PT b) { return a.x * b.y - a.y * b.x; }
inline double cross2(PT a, PT b, PT c) { return cross(b - a, c - a); }
PT perp(PT a) { return PT(-a.y, a.x); }

struct line {
    PT a, b; // goes through points a and b
    PT v; double c;  //line form: direction vec [cross] (x, y) = c
    line() {}
    //direction vector v and offset c
    line(PT v, double c) : v(v), c(c) {
        auto p = get_points();
        a = p.first; b = p.second;
    }
    // equation ax + by + c = 0
    line(double _a, double _b, double _c) : v({_b, -_a}), c(-_c) {
        auto p = get_points();
        a = p.first; b = p.second;
    }
    // goes through points p and q
    line(PT p, PT q) : v(q - p), c(cross(v, p)), a(p), b(q) {}
    pair<PT, PT> get_points() { //extract any two points from this line
        PT p, q; double a = -v.y, b = v.x; // ax + by = c
        if (sign(a) == 0) {
            p = PT(0, c / b);
            q = PT(1, c / b);
        }
        else if (sign(b) == 0) {
            p = PT(c / a, 0);
            q = PT(c / a, 1);
        }
        else {
            p = PT(0, c / b);
            q = PT(1, (c - a) / b);
        }
        return {p, q};
    }
    // ax + by + c = 0
    array<double, 3> get_abc() {
        double a = -v.y, b = v.x;
        return {a, b, -c};
    }
    // 1 if on the left, -1 if on the right, 0 if on the line
    int side(PT p) { return sign(cross(v, p) - c); }
    // line that is perpendicular to this and goes through point p
    line perpendicular_through(PT p) { return {p, p + perp(v)}; }
    // translate the line by vector t i.e. shifting it by vector t
    line translate(PT t) { return {v, c + cross(v, t)}; }
    // compare two points by their orthogonal projection on this line
    // a projection point comes before another if it comes first according to vector v
    bool cmp_by_projection(PT p, PT q) { return dot(v, p) < dot(v, q); }
    line shift_left(double d) {
        PT z = v.perp().truncate(d);
        return line(a + z, b + z);
    }
};

struct circle {
    PT p; double r;
    circle() {}
    circle(PT _p, double _r): p(_p), r(_r) {};
    // center (x, y) and radius r
    circle(double x, double y, double _r): p(PT(x, y)), r(_r) {};
    bool operator == (circle v) { return p == v.p && sign(r - v.r) == 0; }
    double area() { return PI * r * r; }
    double circumference() { return 2.0 * PI * r; }
};

vector<PT> circle_line_intersection(PT c, double r, PT a, PT b) {
    vector<PT> ret;
    b = b - a; a = a - c;
    double A = dot(b, b), B = dot(a, b);
    double C = dot(a, a) - r * r, D = B * B - A * C;
    if (D < -eps) return ret;
    ret.push_back(c + a + b * (-B + sqrt(D + eps)) / A);
    if (D > eps) ret.push_back(c + a + b * (-B - sqrt(D)) / A);
    return ret;
}

PT a,b,c;
double r;

double solve(double t){
    PT p = a + (b-a)*t;
    vector<PT> v = circle_line_intersection(c,r,c,p);
    //assert(v.size()==1);
    PT in = v[0];
    if(v.size()>1){
        if(sign(dist(in,p)-dist(v[1],p))>0) in = v[1];
    }
    return dist(a,in)+dist(b,in);
}

void probG(){
    cin >> a >> b >> c;
    cin >> r;
    if(sign(dist2(a,c)-r)<=0||sign(dist2(b,c)-r)<=0){
        cout << fixed << setprecision(12) << dist(a,b) << endl;
        return;
    }
    double s = 0, e = 1;
    int t = 5000;
    while(t-->0){
        double l = (s*2+e)/3, r = (s+e*2)/3;
        if(solve(l)>solve(r)) s = l;
        else e = r;
    }
    cout << fixed << setprecision(12) << solve(s) << endl;
}
void probI(){
    int i,j,l,n; cin>>n;
    vector<int>deg(n); cout<<"QUERY "; f2(i,n)cout<<1; nl;
    f2(i,n)cin>>deg[i];
    vector<int>in[15];
    f2(j,15){
        cout<<"QUERY "; f2(i,n)cout<<((i>>j)&1); nl;
        in[j].resize(n); f2(i,n)cin>>in[j][i];
    } cout<<"ANSWER\n";
    set<p64>s; f2(i,n)s.insert({deg[i],i});
    while(!s.empty()){
        int x=(*s.begin()).se; s.erase(s.begin()); // node x has deg 1
        int get=0;
        f2(j,15){
            if(in[j][x]==1){
                get|=1<<j;
            }
        } cout<<x+1<<' '<<get+1<<endl;
        // remove x to get from other
        s.erase({deg[get],get}); s.erase({deg[x],x});
        --deg[x]; --deg[get];
        if(deg[x]>0) s.insert({deg[x],x}); if(deg[get]>0) s.insert({deg[get],get});
        f2(j,15) if((get>>j)&1) --in[j][x];
        f2(j,15) if((x>>j)&1) --in[j][get];
    }
}void probJ(){
    int i,j,l;
}void probK(){
    int i,j,l;
}void probL(){
    int i,j,l;
}
i32 main(){
    // fast;
     // int tc; cin>>tc;
     // while(tc--)probG();
    probI();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 121ms
memory: 8832kb

input:

30000
1 1 3 3 1 3 1 1 3 1 3 1 1 3 3 3 3 1 3 3 1 3 3 1 3 1 1 1 3 3 3 3 3 1 1 3 3 3 1 3 3 3 1 3 3 3 3 1 1 3 3 1 3 3 3 1 1 1 3 1 1 3 1 1 3 1 3 1 3 1 3 3 3 3 1 3 1 1 1 3 3 1 3 3 3 3 1 3 1 3 1 3 3 3 3 1 1 3 3 1 3 3 3 1 3 3 1 3 3 3 1 1 3 1 1 1 1 1 3 1 3 1 3 1 1 3 3 3 3 3 3 3 1 1 1 3 1 1 3 3 3 1 1 1 3 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #2:

score: 0
Accepted
time: 64ms
memory: 6400kb

input:

16384
1 3 3 3 3 3 1 1 3 1 3 3 3 3 3 1 1 1 1 3 3 3 3 3 1 1 3 1 1 1 3 3 3 3 1 1 1 3 3 1 3 3 3 3 1 1 1 3 1 3 3 1 3 1 3 1 1 3 1 3 3 1 3 1 1 3 1 3 1 3 3 3 3 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 3 1 1 3 1 3 1 1 1 1 3 1 1 3 1 1 3 3 3 1 1 3 1 3 1 1 1 1 3 1 1 1 3 3 1 3 1 3 3 1 1 1 3 3 3 1 1 1 1 1 3 1 1 1 3 1 3 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

8
1 3 2 1 3 1 1 2
1 0 1 0 2 1 1 1
0 2 0 0 3 1 0 0
0 1 1 1 1 1 0 2
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:

QUERY 11111111
QUERY 01010101
QUERY 00110011
QUERY 00001111
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 2
4 5
6 8
7 2
2 3
3 5
5 8

result:

ok correct answer

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4
1 1 1 3
1 1 1 1
1 1 1 1
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:

QUERY 1111
QUERY 0101
QUERY 0011
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
ANSWER
1 4
2 4
3 4

result:

ok correct answer

Test #5:

score: 0
Accepted
time: 116ms
memory: 8832kb

input:

30000
1 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 1 2 2 2 2 2 2 3 2 3 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 2 2 2 3 2 2 2 2 2 2 2 1 2 2 2 1 3 1 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 1 2 3 2 3 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #6:

score: 0
Accepted
time: 118ms
memory: 8960kb

input:

29999
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 1 2 2 2 3 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 4 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 1 2 1 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #7:

score: 0
Accepted
time: 121ms
memory: 8704kb

input:

30000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #8:

score: 0
Accepted
time: 120ms
memory: 8704kb

input:

29997
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #9:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

8
2 2 2 1 2 2 1 2
2 1 1 0 1 0 1 1
1 2 0 0 2 1 0 0
1 2 2 0 1 0 0 1
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:

QUERY 11111111
QUERY 01010101
QUERY 00110011
QUERY 00001111
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
4 1
1 6
6 3
3 5
5 8
7 2
2 8

result:

ok correct answer

Test #10:

score: 0
Accepted
time: 117ms
memory: 8832kb

input:

30000
2 2 1 4 10 4 3 1 1 1 1 1 4 1 1 1 2 4 2 3 1 2 4 1 1 3 1 5 1 1 5 3 1 1 2 2 1 4 1 3 3 2 2 2 2 1 1 2 3 4 3 4 1 2 2 3 1 1 1 1 1 1 3 2 1 2 2 1 1 2 1 2 2 2 1 1 3 1 4 1 2 1 3 2 1 2 1 1 1 3 1 7 2 1 2 1 1 6 2 1 5 4 1 1 2 1 1 1 3 1 1 1 1 1 1 4 3 3 2 1 2 1 2 1 1 1 5 1 4 2 1 1 1 1 4 1 1 2 1 7 2 1 1 1 1 1 1...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #11:

score: 0
Accepted
time: 120ms
memory: 8832kb

input:

29999
4 2 3 2 2 1 2 4 3 3 3 1 6 2 1 2 1 2 2 1 1 1 1 3 3 1 2 4 1 1 1 2 4 7 3 1 1 2 1 2 2 1 1 3 5 4 3 1 1 1 1 2 1 2 1 2 3 1 1 4 1 1 7 1 1 1 2 1 1 2 9 3 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 4 2 1 1 3 2 1 2 1 1 1 1 1 1 1 2 1 1 2 4 8 4 3 1 1 5 3 1 3 3 1 5 1 1 5 1 1 1 6 2 2 2 1 2 1 1 1 1 4 1 6 3 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #12:

score: 0
Accepted
time: 121ms
memory: 8832kb

input:

30000
1 4 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 1 1 3 1 1 1 7 3 2 5 1 1 9 1 1 4 1 1 4 2 1 2 1 1 1 3 3 1 1 1 1 2 4 4 6 1 2 2 1 1 1 2 2 2 1 2 1 3 3 3 2 1 1 1 1 1 1 1 4 2 1 2 1 1 2 1 3 5 1 1 2 2 1 2 3 1 3 1 1 1 2 1 2 2 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 2 4 2 3 1 2 2 2 3 2 1 2 3 1 1 2 1 1 3 1 1 5 2 1 1 2 2 1 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #13:

score: 0
Accepted
time: 122ms
memory: 8960kb

input:

29997
5 1 1 1 2 5 1 1 3 1 3 1 5 2 1 1 2 2 4 2 1 4 2 1 4 1 1 2 1 1 1 2 1 1 2 8 1 4 4 1 2 3 2 1 3 1 2 2 2 5 1 4 2 2 3 2 2 2 3 3 2 2 7 4 4 4 1 5 5 2 1 4 1 1 2 2 5 1 1 3 3 1 3 1 1 1 1 2 1 4 3 4 3 2 1 2 2 1 1 1 2 1 3 1 1 1 2 2 2 2 1 2 4 4 3 2 1 3 1 2 1 2 1 1 3 3 3 2 3 2 1 1 2 1 1 1 1 2 2 1 1 2 2 1 1 1 6 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #14:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

10
2 1 3 2 1 1 2 2 1 3
2 1 1 1 1 0 1 0 0 2
1 0 2 1 1 1 1 0 1 1
1 0 1 0 1 1 1 1 0 0
1 1 1 1 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:

QUERY 1111111111
QUERY 0101010101
QUERY 0011001100
QUERY 0000111100
QUERY 0000000011
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
ANSWER
2 10
5 8
6 7
7 3
8 1
...

result:

ok correct answer

Test #15:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

8
1 1 2 3 4 1 1 1
0 0 0 1 3 0 1 1
1 0 0 2 2 0 1 1
0 1 1 3 1 1 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:

QUERY 11111111
QUERY 01010101
QUERY 00110011
QUERY 00001111
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 3
2 5
3 5
6 5
5 4
7 4
4 8

result:

ok correct answer

Test #16:

score: 0
Accepted
time: 120ms
memory: 8704kb

input:

30000
2 1 2 3 1 1 5 3 1 5 3 1 4 1 3 1 1 1 1 2 1 1 1 1 6 2 2 2 1 3 1 6 3 4 1 3 1 1 2 1 1 1 1 3 1 3 1 2 1 1 1 1 1 5 3 5 1 3 1 1 1 1 1 4 2 3 1 1 1 1 3 1 2 1 1 1 1 3 4 1 2 2 1 2 3 1 1 2 1 1 1 2 1 1 1 1 1 1 1 2 2 1 2 2 2 1 3 3 3 4 2 4 2 1 2 1 1 4 1 2 3 4 1 1 1 1 1 2 1 2 1 1 2 6 3 1 2 1 1 3 1 2 2 1 1 2 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #17:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

128
1 2 2 7 3 1 2 2 3 4 1 4 1 1 3 1 1 1 4 3 2 1 3 1 2 1 5 1 2 2 3 1 1 3 3 2 1 1 1 3 1 3 1 1 1 2 3 3 4 3 2 1 7 1 4 1 1 4 4 3 1 3 2 1 2 1 1 1 2 1 1 1 1 1 1 2 3 1 1 1 1 2 2 1 1 1 1 3 2 1 1 1 3 1 1 1 3 2 2 1 3 3 1 3 4 1 1 1 7 1 1 4 1 1 3 2 1 2 2 2 1 6 2 1 1 2 1 1
1 1 2 5 1 0 1 0 2 3 0 0 0 1 0 1 0 1 3 1 ...

output:

QUERY 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
QUERY 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
QUERY 001100110011001100110011...

result:

ok correct answer

Test #18:

score: 0
Accepted
time: 111ms
memory: 8832kb

input:

30000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #19:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

3
1 1 2
0 0 1
1 1 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:

QUERY 111
QUERY 010
QUERY 001
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
ANSWER
1 3
2 3

result:

ok correct answer

Test #20:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

2
1 1
1 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:

QUERY 11
QUERY 01
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
ANSWER
1 2

result:

ok correct answer