답안 #259853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259853	2020-08-08T17:18:52 Z	Osama_Alkhodairy	Xoractive (IZhO19_xoractive)	C++17	90 / 100	4 ms	512 KB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"
//~ #include "grader.cpp"
using namespace std;

vector <int> get(vector <int> &c){
    if(c.size() == 0) return {};
    auto d = get_pairwise_xor(c);
    reverse(d.begin(), d.end());
    while(d.size() && d.back() == 0){
        d.pop_back();
    }
    vector <int> ret;
    for(int i = 1 ; i < (int)d.size() ; i += 2){
        ret.push_back(d[i]);
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
vector <int> intersect(vector <int> a, vector <int> b){
    vector <int> ret;
    while(a.size() && b.size()){
        if(a.back() == b.back()){
            ret.push_back(a.back());
            a.pop_back();
            b.pop_back();
        }
        else if(a.back() > b.back()){
            a.pop_back();
        }
        else{
            b.pop_back();
        }
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
vector <int> del(vector <int> a, vector <int> b){
    vector <int> ret;
    while(a.size()){
        if(b.size()){
            if(b.back() > a.back()){
                b.pop_back();
                continue;
            }
            else if(b.back() == a.back()){
                a.pop_back();
                b.pop_back();
                continue;
            }
        }
        ret.push_back(a.back());
        a.pop_back();
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
vector <int> guess(int n) {
    vector <int> ans(n + 1);
    int p = 0;
    while((1 << (p + 1)) <= n){
        p++;
    }
    ans[(1 << p) - 1] = ask((1 << p) - 1);
    ans[1 << p] = ask(1 << p);
    vector <vector <int> > f(10);
    for(int i = 0 ; i <= p ; i++){
        vector <int> all;
        for(int j = 1 ; j <= n ; j++){
            if((j >> i) & 1) all.push_back(j);
        }
        int m = i == p ? (1 << p) : (1 << p) - 1;
        auto g = get(all);
        all.erase(find(all.begin(), all.end(), m));
        auto h = get(all);
        f[i] = del(g, h);
        f[i].push_back(0);
        for(auto &j : f[i]) j ^= ans[m];
    }
    vector <int> all;
    for(int i = 0 ; i < 10 ; i++){
        sort(f[i].begin(), f[i].end());
        for(auto &j : f[i]){
            all.push_back(j);
        }
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    for(int i = 1 ; i <= n ; i++){
        vector <int> cands = all;
        for(int j = 0 ; j < 10 ; j++){
            if((i >> j) & 1){
                cands = intersect(cands, f[j]);
            }
            else{
                cands = del(cands, f[j]);
            }
        }
        ans[i] = cands[0];
    }
    ans.erase(ans.begin());
    return ans;
}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct

Subtask #2

84.0 / 94.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	3 ms	384 KB	Output is partially correct
2	Partially correct	3 ms	384 KB	Output is partially correct
3	Partially correct	2 ms	384 KB	Output is partially correct
4	Partially correct	3 ms	416 KB	Output is partially correct
5	Partially correct	3 ms	384 KB	Output is partially correct
6	Partially correct	3 ms	384 KB	Output is partially correct
7	Partially correct	2 ms	384 KB	Output is partially correct
8	Partially correct	3 ms	384 KB	Output is partially correct
9	Partially correct	3 ms	512 KB	Output is partially correct
10	Partially correct	3 ms	384 KB	Output is partially correct
11	Partially correct	2 ms	364 KB	Output is partially correct
12	Partially correct	3 ms	256 KB	Output is partially correct
13	Partially correct	2 ms	384 KB	Output is partially correct
14	Partially correct	3 ms	368 KB	Output is partially correct
15	Partially correct	2 ms	384 KB	Output is partially correct
16	Partially correct	3 ms	384 KB	Output is partially correct
17	Partially correct	3 ms	384 KB	Output is partially correct
18	Partially correct	3 ms	384 KB	Output is partially correct
19	Partially correct	2 ms	384 KB	Output is partially correct
20	Partially correct	3 ms	364 KB	Output is partially correct
21	Partially correct	3 ms	384 KB	Output is partially correct
22	Partially correct	4 ms	384 KB	Output is partially correct
23	Partially correct	3 ms	384 KB	Output is partially correct
24	Partially correct	3 ms	384 KB	Output is partially correct
25	Partially correct	3 ms	384 KB	Output is partially correct
26	Partially correct	3 ms	384 KB	Output is partially correct
27	Partially correct	3 ms	384 KB	Output is partially correct
28	Partially correct	3 ms	384 KB	Output is partially correct
29	Partially correct	3 ms	384 KB	Output is partially correct
30	Partially correct	3 ms	384 KB	Output is partially correct
31	Partially correct	3 ms	512 KB	Output is partially correct
32	Partially correct	3 ms	384 KB	Output is partially correct
33	Partially correct	3 ms	384 KB	Output is partially correct
34	Partially correct	3 ms	368 KB	Output is partially correct
35	Partially correct	2 ms	384 KB	Output is partially correct
36	Partially correct	3 ms	384 KB	Output is partially correct
37	Partially correct	3 ms	384 KB	Output is partially correct
38	Partially correct	3 ms	384 KB	Output is partially correct
39	Partially correct	2 ms	384 KB	Output is partially correct
40	Partially correct	3 ms	384 KB	Output is partially correct
41	Partially correct	3 ms	384 KB	Output is partially correct
42	Partially correct	3 ms	384 KB	Output is partially correct
43	Partially correct	2 ms	384 KB	Output is partially correct
44	Partially correct	3 ms	384 KB	Output is partially correct
45	Partially correct	3 ms	384 KB	Output is partially correct
46	Partially correct	3 ms	384 KB	Output is partially correct
47	Partially correct	2 ms	384 KB	Output is partially correct
48	Partially correct	3 ms	384 KB	Output is partially correct
49	Partially correct	3 ms	384 KB	Output is partially correct
50	Partially correct	3 ms	384 KB	Output is partially correct
51	Partially correct	3 ms	384 KB	Output is partially correct
52	Partially correct	3 ms	384 KB	Output is partially correct
53	Partially correct	4 ms	384 KB	Output is partially correct
54	Partially correct	4 ms	384 KB	Output is partially correct
55	Partially correct	2 ms	384 KB	Output is partially correct
56	Partially correct	3 ms	384 KB	Output is partially correct
57	Partially correct	3 ms	384 KB	Output is partially correct
58	Partially correct	3 ms	384 KB	Output is partially correct
59	Partially correct	2 ms	384 KB	Output is partially correct
60	Partially correct	3 ms	384 KB	Output is partially correct
61	Partially correct	3 ms	384 KB	Output is partially correct
62	Partially correct	3 ms	384 KB	Output is partially correct
63	Partially correct	3 ms	384 KB	Output is partially correct
64	Partially correct	3 ms	384 KB	Output is partially correct
65	Partially correct	3 ms	384 KB	Output is partially correct
66	Partially correct	3 ms	384 KB	Output is partially correct
67	Partially correct	3 ms	384 KB	Output is partially correct
68	Partially correct	3 ms	384 KB	Output is partially correct
69	Partially correct	3 ms	384 KB	Output is partially correct
70	Partially correct	3 ms	384 KB	Output is partially correct
71	Partially correct	3 ms	384 KB	Output is partially correct
72	Partially correct	3 ms	384 KB	Output is partially correct
73	Partially correct	3 ms	384 KB	Output is partially correct
74	Partially correct	3 ms	308 KB	Output is partially correct
75	Partially correct	3 ms	384 KB	Output is partially correct
76	Partially correct	3 ms	384 KB	Output is partially correct
77	Partially correct	3 ms	384 KB	Output is partially correct
78	Partially correct	3 ms	384 KB	Output is partially correct
79	Partially correct	2 ms	384 KB	Output is partially correct
80	Partially correct	3 ms	384 KB	Output is partially correct
81	Partially correct	3 ms	384 KB	Output is partially correct
82	Partially correct	3 ms	384 KB	Output is partially correct
83	Partially correct	2 ms	384 KB	Output is partially correct
84	Partially correct	4 ms	384 KB	Output is partially correct
85	Partially correct	3 ms	384 KB	Output is partially correct
86	Partially correct	3 ms	384 KB	Output is partially correct
87	Partially correct	2 ms	384 KB	Output is partially correct
88	Partially correct	3 ms	384 KB	Output is partially correct
89	Partially correct	3 ms	384 KB	Output is partially correct
90	Partially correct	3 ms	384 KB	Output is partially correct
91	Partially correct	2 ms	384 KB	Output is partially correct
92	Partially correct	3 ms	384 KB	Output is partially correct
93	Partially correct	3 ms	384 KB	Output is partially correct
94	Partially correct	3 ms	384 KB	Output is partially correct
95	Partially correct	2 ms	384 KB	Output is partially correct
96	Partially correct	3 ms	384 KB	Output is partially correct
97	Partially correct	3 ms	384 KB	Output is partially correct
98	Partially correct	3 ms	384 KB	Output is partially correct
99	Partially correct	2 ms	384 KB	Output is partially correct
100	Partially correct	3 ms	384 KB	Output is partially correct