QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137702#6627. Line Townpenguinman#0 1ms3932kbC++176.7kb2023-08-10 16:44:042024-07-04 01:29:57

Judging History

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

  • [2024-07-04 01:29:57]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：3932kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 16:44:04]
  • 提交

answer

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);

template<typename T>
struct segment_tree{
    ll N, valINF;
    vector<T> node;
    segment_tree(int n, T valINF_){
        valINF = valINF_;
        N = 1;
        while(N <= n) N *= 2;
        node.resize(2*N, valINF);
    }
    void update(ll idx, T val){
        idx += N;
        node[idx] = val;
        idx /= 2;
        while(idx){
            node[idx] = compare(node[idx*2], node[idx*2+1]);
            idx /= 2;
        }
    }
    T calc(ll l, ll r){
        T ret = valINF;
        l += N;
        r += N;
        r--;
        while(l < r){
            if(l & 1){
                ret = compare(ret, node[l]);
                l++;
            }
            l /= 2;
            if((r&1) == 0){
                ret = compare(ret, node[r]);
                r--;
            }
            r /= 2;
        }
        if(l == r) ret = compare(ret, node[l]);
        return ret;
    }
    T compare(T l, T r){
        return std::min(l, r);
    }
};

template<typename T>
struct binary_indexed_tree{
    ll N;
    vector<T> node;
    binary_indexed_tree(int n){
        N = n;
        node.resize(N+1);
    }
    void add(ll idx, ll val){
        idx++;
        for(; idx<=N; idx+=(idx&(-idx))){
            node[idx] += val;
        }
    }
    T sum(ll idx){
        idx++;
        T ret = 0;
        for(; 0<idx; idx-=(idx&(-idx))){
            ret += node[idx];
        }
        return ret;
    }
};

int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll N; cin >> N;
    vi A(N);
    rep(i,0,N) cin >> A[i];
    vector<pii> data(N);
    rep(i,0,N) data[i] = mp(std::abs(A[i]), i);
    sort(all(data));
    reverse(all(data));
    string S = "";
    vi idx;
    for(auto &el: data){
        if(el.second%2) el.first = -A[el.second];
        else el.first = A[el.second];
        if(el.first == 0) S += '2';
        else if(el.first > 0) S += '1';
        else S += '0';
        idx.pb(el.second);
    }
    ll ans = inf;
    if(S[0] == '0'){
        string now = "10";
        rep(i,0,N){
            vi cand;
            rep(j,0,2){
                if(now[j] != S[i]) cand.pb(j);
            }
            if(cand.empty()) goto XYZ;
            now[cand[0]] = S[i];
        }
        now = "10";
        binary_indexed_tree<ll> remain(N+1);
        rep(i,0,N) remain.add(idx[i],1);
        ll cost = 0;
        rep(i,0,N){
            vi cand;
            rep(j,0,2){
                if(now[j] != S[i]) cand.pb(j);
            }
            if(cand.empty()) goto XYZ;
            if(cand.size() == 2){
                if(i+1 == N){
                    remain.add(idx[i], -1);
                    break;
                }
                else if(S[i+1] == S[i]){
                    now[0] = now[1] = S[i];
                    remain.add(idx[i], -1);
                    remain.add(idx[i+1], -1);
                    cost += remain.sum(N)-remain.sum(std::max(idx[i], idx[i+1]));
                    cost += remain.sum(std::min(idx[i], idx[i+1]));
                    i++;
                }
                else if(S[i+1] != '2'){
                    remain.add(idx[i], -1);
                    remain.add(idx[i+1], -1);
                    ll l = 0, r = 0;
                    l += remain.sum(N)-remain.sum(idx[i]);
                    l += remain.sum(N)-remain.sum(idx[i+1]);
                    if(idx[i+1] > idx[i]) l++;
                    r += remain.sum(idx[i+1]);
                    r += remain.sum(idx[i]);
                    if(idx[i] > idx[i+1]) r++;
                    cost += std::min(l, r);
                    i++;
                }
                else{
                    remain.add(idx[i], -1);
                    remain.add(idx[i+1], -1);
                    break;
                }
            }
            else{
                assert(i == 0);
                remain.add(idx[i], -1);
                if(S[i] == '0'){
                    now[0] = '0';
                    cost += remain.sum(idx[i]);
                }
                else{
                    now[1] = '1';
                    cost += remain.sum(N)-remain.sum(idx[i]);
                }
            }
        }
        ans = std::min(ans, cost);
    }
    XYZ:;
    {
        string now = "11";
        rep(i,0,N){
            vi cand;
            rep(j,0,2){
                if(now[j] != S[i]) cand.pb(j);
            }
            if(cand.empty()) goto WXY;
            now[cand[0]] = S[i];
        }
        now = "11";
        binary_indexed_tree<ll> remain(N+1);
        rep(i,0,N) remain.add(idx[i],1);
        ll cost = 0;
        rep(i,0,N){
            vi cand;
            rep(j,0,2){
                if(now[j] != S[i]) cand.pb(j);
            }
            if(cand.empty()) goto XYZ;
            if(cand.size() == 2){
                if(i+1 == N){
                    remain.add(idx[i], -1);
                }
                else if(S[i+1] == S[i]){
                    now[0] = now[1] = S[i];
                    remain.add(idx[i], -1);
                    remain.add(idx[i+1], -1);
                    cost += remain.sum(N)-remain.sum(std::max(idx[i], idx[i+1]));
                    cost += remain.sum(std::min(idx[i], idx[i+1]));
                    i++;
                }
                else if(S[i+1] != '2'){
                    remain.add(idx[i], -1);
                    remain.add(idx[i+1], -1);
                    ll l = 0, r = 0;
                    l += remain.sum(N)-remain.sum(idx[i]);
                    l += remain.sum(N)-remain.sum(idx[i+1]);
                    if(idx[i+1] > idx[i]) l++;
                    r += remain.sum(idx[i+1]);
                    r += remain.sum(idx[i]);
                    if(idx[i] > idx[i+1]) r++;
                    cost += std::min(l, r);
                    i++;
                }
                else{
                    remain.add(idx[i], -1);
                    remain.add(idx[i+1], -1);
                    break;
                }
            }
            else{
                assert(false);
            }
        }
        ans = std::min(ans, cost);
    }
    WXY:;
    if(ans == inf) ans = -1;
    cout << ans << ln;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 3
Accepted
time: 0ms
memory: 3612kb

input:

10
1 1 1 1 1 -1 -1 -1 1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #2:

score: -3
Wrong Answer
time: 0ms
memory: 3828kb

input:

10
1 1 1 1 1 1 -1 1 1 -1

output:

-1

result:

wrong answer 1st numbers differ - expected: '3', found: '-1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #60:

score: 4
Accepted
time: 0ms
memory: 3604kb

input:

10
3 10 5 -9 7 2 -6 1 8 0

output:

-1

result:

ok 1 number(s): "-1"

Test #61:

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

input:

10
-9 0 -1 7 5 10 6 3 2 -8

output:

13

result:

ok 1 number(s): "13"

Test #62:

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

input:

2000
40667 -598150 -1084780 1201651 1570514 -1859539 -2029075 2941581 -2945945 3038404 3447919 5293872 -5335692 -5669647 5973784 6041345 6346915 -7222112 8820986 -9153143 9563103 9749206 -9894732 -11847193 11987150 12161864 13336572 13528051 -13722732 -13836176 -15497141 -15841563 15862227 16618123 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #63:

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

input:

2000
3038404 -798315545 693574695 172661079 516504064 164016456 193562146 -131746730 382134316 -398886978 188767854 -834289064 -965673210 -826409444 -281381674 450991903 -592752625 81651101 -594873306 -352059270 -651772982 540062674 -769881300 68999588 307151563 -129950325 550154987 354801227 840540...

output:

658039

result:

ok 1 number(s): "658039"

Test #64:

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

input:

2000
-1095 -925 -1049 -1519 951 -1673 -776 345 -38 -1735 -276 -1730 123 -1629 -1896 -1576 -1115 1145 15 797 -948 287 1487 1195 1269 -1240 -1571 -275 -1915 -369 -1221 -1590 -1392 -100 1688 -1287 -241 1130 -1375 -965 669 -147 -307 -795 -1207 1939 120 -305 -915 -1078 -1448 1458 -603 1935 658 774 1471 7...

output:

668545

result:

ok 1 number(s): "668545"

Test #65:

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

input:

2000
1290 1487 -1947 -255 457 -1202 1313 36 -1511 898 1739 987 1809 -1986 -1015 -1127 -703 -223 179 557 199 349 1099 -259 -1401 -1244 -1116 646 -295 1713 1512 127 -1660 343 -1921 -1326 -549 831 1963 -1743 1655 -698 1792 366 1517 -51 404 -1853 -1295 1652 -130 -1562 -1850 -582 1504 1888 822 -24 1807 9...

output:

663841

result:

ok 1 number(s): "663841"

Test #66:

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

input:

2000
56 -1667 -1636 -671 -1311 348 976 1381 -710 -477 -1301 756 -510 495 -1215 -278 1134 950 59 1739 -33 -839 -862 605 761 827 -1708 -1180 -607 1624 -120 -1198 624 -1237 -1874 1788 1005 -331 1266 -467 -1213 1736 -182 594 775 1209 -832 300 1188 -994 -191 -217 1360 -1907 71 436 1294 -590 913 -747 -629...

output:

667052

result:

ok 1 number(s): "667052"

Test #67:

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

input:

1999
-758656 -113741 -374719 7680 -227905 -201318 -200890 -84484 777096 -167712 -126972 -244117 835074 161027 923025 -224756 973701 36622 -913757 -920737 -976062 461264 147694 -162457 358437 -308202 385370 808271 -523703 -303454 -522131 -664739 -505124 306509 948216 948694 -467953 -768055 769796 486...

output:

675957

result:

ok 1 number(s): "675957"

Test #68:

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

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #69:

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

input:

2
1000000000 999999999

output:

-1

result:

ok 1 number(s): "-1"

Test #70:

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

input:

2000
999998002 999998004 999998006 999998008 999998010 999998012 999998014 999998016 999998018 999998020 999998022 999998024 999998026 999998028 999998030 999998032 999998034 999998036 999998038 999998040 999998042 999998044 999998046 999998048 999998050 999998052 999998054 999998056 999998058 99999...

output:

999000

result:

ok 1 number(s): "999000"

Test #71:

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

input:

1999
-1000000000 -999012346 -998024692 -997037038 -996049384 -995061730 -994074076 -993086422 -992098768 -991111114 -990123460 -989135806 -988148152 -987160498 -986172844 -985185190 -984197536 -983209882 -982222228 -981234574 -980246920 -979259266 -978271612 -977283958 -976296304 -975308650 -9743209...

output:

0

result:

ok 1 number(s): "0"

Test #72:

score: -4
Wrong Answer
time: 0ms
memory: 3616kb

input:

1999
1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 1941 1940 ...

output:

-1

result:

wrong answer 1st numbers differ - expected: '1998', found: '-1'

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 23:30:41 | OpenSource Project