QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489621#8819. CNOI Knowledge_log_WA 246ms28256kbC++172.5kb2024-07-24 21:57:012024-07-24 21:57:01

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 21:57:01]
  • 评测
  • 测评结果:WA
  • 用时:246ms
  • 内存:28256kb
  • [2024-07-24 21:57:01]
  • 提交

answer

# include <bits/stdc++.h>
# define maxn 1005
# define ull unsigned long long
# define rep(i, j, k) for(int i = j; i <= k; ++i)
using namespace std;

int n, a[maxn], tot;
int Hash1[maxn], d[maxn], pw[maxn];
int ans[maxn][maxn];
map<ull, int> mp;

namespace Garder {
    int ans[10][10];
    void init() {
        ans[1][1] = 1; ans[1][2] = 3, ans[1][3] = 6; ans[1][4] = 9; ans[1][5] = 12; ans[1][6] = 18; ans[1][7] = 24; ans[1][8] = 31;
        ans[2][2] = 1; ans[2][3] = 3; ans[2][4] = 5; ans[2][5] = 7; ans[2][6] = 12; ans[2][7] = 17; ans[2][8] = 24;
        ans[3][3] = 1; ans[3][4] = 3; ans[3][5] = 5; ans[3][6] = 9; ans[3][7] = 13; ans[3][8] = 19;
        ans[4][4] = 1; ans[4][5] = 3; ans[4][6] = 6; ans[4][7] = 9; ans[4][8] = 14;
        ans[5][5] = 1; ans[5][6] = 3; ans[5][7] = 6; ans[5][8] = 10;
        ans[6][6] = 1; ans[6][7] = 3; ans[6][8] = 6;
        ans[7][7] = 1; ans[7][8] = 3;
        ans[8][8] = 1;
    }
}

int query(int l, int r) {
    cout << "? " << l << ' ' << r << endl;
    // cout << Garder::ans[l][r] << endl;
    // ans[l][r] = Garder::ans[l][r];
    cin >> ans[l][r];
    return ans[l][r];
}

void update(int r) {
    Hash1[r] = Hash1[r - 1] * 19260817 + a[r];
    rep(i, 1, r) {
        int hsh = Hash1[r] - Hash1[i - 1] * pw[r - i + 1], l = mp[hsh], len = r - i + 1;
        // cerr << i << ' ' << r << ' ' << hsh << '\n';
        if(!l) d[1]++, d[i + 1]--;
        else d[l - len + 2]++, d[i + 1]--;
        mp[hsh] = r;
    }
    rep(i, 1, r) d[i] = d[i - 1] + d[i];//, cerr << d[i] << ' '; cerr << '\n';
    rep(i, 1, r) ans[i][r] = ans[i][r - 1] + d[i];//, cout << ans[i][r] << ' '; cout << '\n';
    memset(d, 0, sizeof(d));
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); Garder::init();
    // memset(ans, -1, sizeof(ans));
    cin >> n; a[1] = ++tot; Hash1[1] = 1;  ans[1][1] = 1; mp[1] = 1;
    pw[0] = 1; rep(i, 1, n) pw[i] = pw[i - 1] * 19260817;
    rep(i, 2, n) {
    	// rep(j, 1, i - 1) cout << ans[j][i - 1] << ' '; cout << '\n';
        if(query(1, i) - ans[1][i - 1] == i) {a[i] = ++tot; update(i); continue;}
        int l = 1, r = i, pos;
        while(l <= r) {
            int mid = l + r >> 1;
            if(query(mid, i) - ans[mid][i - 1] == i - mid + 1) pos = mid - 1, r = mid - 1;
            else l = mid + 1;
        }
        a[i] = a[pos];
        update(i);
//        cout << "pos " << pos << ' ' << tot << '\n';
//        rep(j, 1, i) cout << a[i] << ' '; cout << '\n';
    }
    cout << "! ";
    rep(i, 1, n) cout << a[i] << ' ';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

input:

12
3
6
10
15
21
27
10
20
15
34
14
6
9
43
52
19
5
2
1
62
19
5
13
8
72
25
9
19

output:

? 1 2
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 4 7
? 2 7
? 3 7
? 1 8
? 4 8
? 6 8
? 5 8
? 1 9
? 1 10
? 5 10
? 8 10
? 9 10
? 10 10
? 1 11
? 6 11
? 9 11
? 7 11
? 8 11
? 1 12
? 6 12
? 9 12
? 7 12
! 1 2 3 4 5 6 2 5 7 7 5 6 

result:

ok Accepted. 28 queries used.

Test #2:

score: -100
Wrong Answer
time: 246ms
memory: 28256kb

input:

1000
3
5
2
1
7
3
2
1
11
5
11
7
16
8
2
1
21
7
2
1
27
11
5
7
34
11
5
3
41
15
5
2
1
48
15
3
2
1
57
19
4
2
1
66
17
4
2
1
75
20
4
2
1
84
15
4
2
1
96
23
9
13
15
108
23
11
5
3
124
31
11
5
3
140
36
11
5
2
1
156
45
15
3
2
1
172
48
15
5
11
7
188
58
16
5
2
1
208
59
16
5
12
8
229
69
21
8
2
1
251
69
20
8
3
5
273...

output:

? 1 2
? 1 3
? 2 3
? 3 3
? 1 4
? 2 4
? 3 4
? 4 4
? 1 5
? 3 5
? 1 5
? 2 5
? 1 6
? 3 6
? 5 6
? 6 6
? 1 7
? 4 7
? 6 7
? 7 7
? 1 8
? 4 8
? 6 8
? 5 8
? 1 9
? 5 9
? 7 9
? 8 9
? 1 10
? 5 10
? 8 10
? 9 10
? 10 10
? 1 11
? 6 11
? 9 11
? 10 11
? 11 11
? 1 12
? 6 12
? 9 12
? 11 12
? 12 12
? 1 13
? 7 13
? 10 13
...

result:

wrong answer Wrong Answer.