結果

問題 No.619 CardShuffle
ユーザー Sebastian King
提出日時 2017-12-19 18:20:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 655 ms / 3,000 ms
コード長 2,610 bytes
コンパイル時間 1,915 ms
コンパイル使用メモリ 160,180 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-22 22:33:36
合計ジャッジ時間 11,720 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve(int)’:
main.cpp:88:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:90:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   90 |                 scanf("%s", s);
      |                 ~~~~~^~~~~~~~~
main.cpp:103:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  103 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
main.cpp:106:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  106 |                 scanf("%s", s);
      |                 ~~~~~^~~~~~~~~
main.cpp:107:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |                 scanf("%d%d", &x, &y);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MM = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 10;
int n, m;
void prework(){
}
void read(){
}
char s[100];
ll a[MAXN];
int L[MAXN], R[MAXN];
const int MAKI = 9;
struct node{
    int tp;
    ll a, b, c;
} rst[MAXN], nico;
void Getans(node &ret, int l, int r){
    int p = -1, q = -1;
    for (int i = l + 1; i < r; i += 2)
        if (a[i] == -1){
            if (p == -1) p = i;
            q = i;
        }
    if (p == -1){
        ret.tp = 1;
        ll tmp = 1;
        for (int i = l; i <= r; i += 2)
            tmp = (tmp * a[i] % MM);
        ret.a = tmp;
    }
    else{
        ret.tp = 2;
        ll tmp = 1;
        for (int i = l; i < p; i += 2)
            tmp = (tmp * a[i] % MM);
        ret.a = tmp;
        tmp = 1;
        for (int i = q + 1; i <= r; i += 2)
            tmp = tmp * a[i] % MM;
        ret.c = tmp;
        ll sum = 0;
        tmp = 1;
        for (int i = p + 1; i < q; i += 2){
            tmp = tmp * a[i] % MM;
            if (a[i + 1] == -1){
                sum = (sum + tmp) % MM;
                tmp = 1;
            }
        }
        ret.b = sum;
    }
}
void fill_in(int &pos, node &x, int opt){
    if (x.tp == 1){
        a[pos++] = x.a;
        a[pos++] = opt;
    }
    else{
        a[pos++] = x.a;
        a[pos++] = -1;
        a[pos++] = x.b;
        a[pos++] = -1;
        a[pos++] = x.c;
        a[pos++] = opt;
    }
}
void solve(int casi){
//  cout << "Case #" << casi << ": ";
    int M, Q;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%s", s);
        if (s[0] == '+') a[i] = -1;
        else if (s[0] == '*') a[i] = -2;
        else a[i] = s[0] - '0';
    }
    M = n >> MAKI;
    for (int i = 0; i <= M; i++){
        L[i] = (i << MAKI) + 1;
        R[i] = ((i + 1) << MAKI) - 1;
    }
    L[0] = 1, R[M] = n;
    for (int i = 0; i <= M; i++)
        Getans(rst[i], L[i], R[i]);
    scanf("%d", &Q);
    while(Q--){
        int x, y;
        scanf("%s", s);
        scanf("%d%d", &x, &y);
        int p = x >> MAKI, q = y >> MAKI;
        if (s[0] == '?'){
            int l = n + 2, r = n + 2;
            if (p == q || p + 1 == q){
                Getans(nico, x, y);
                if (nico.tp == 1) printf("%lld\n", nico.a);
                else printf("%lld\n", (nico.a+nico.b+nico.c)%MM);
            }
            else{
                Getans(nico, x, R[p]);
                fill_in(r, nico, a[R[p] + 1]);
                for (int i = p + 1; i < q; i++)
                    fill_in(r, rst[i], a[R[i] + 1]);
                Getans(nico, L[q], y);
                fill_in(r, nico, -1);
                r -= 2;
                Getans(nico, l, r);
                if (nico.tp == 1) printf("%lld\n", nico.a);
                else printf("%lld\n", (nico.a+nico.b+nico.c)%MM);
            }
        }
        else{
            swap(a[x], a[y]);
            Getans(rst[p], L[p], R[p]);
            Getans(rst[q], L[q], R[q]);
        }
    }
}
void printans(){
}
int main(){
//  std::ios::sync_with_stdio(false);
    prework();
    int T = 1;
//  cin>>T;
    for(int i = 1; i <= T; i++){
        read();
        solve(i);
        printans();
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0