結果
| 問題 |
No.619 CardShuffle
|
| コンテスト | |
| ユーザー |
 yuya178
|
| 提出日時 | 2017-12-19 01:46:53 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,779 bytes |
| コンパイル時間 | 2,610 ms |
| コンパイル使用メモリ | 81,084 KB |
| 実行使用メモリ | 134,372 KB |
| 最終ジャッジ日時 | 2024-12-22 21:39:45 |
| 合計ジャッジ時間 | 63,336 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 WA * 4 RE * 6 TLE * 14 |
ソースコード
import java.io.*;
import java.util.*;
import java.math.*;
// import java.awt.Point;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "";
long MOD = 1_000_000_007;
int inf = Integer.MAX_VALUE;
void solve(){
int n = ni();
int[] num = new int[(n+1)/2];
char[] exe = new char[n/2];
String[] s = ns().split(" ");
for(int i = 0; i < n; i++){
if(i%2==0) num[i/2] = Integer.parseInt(s[i]);
else exe[i/2] = s[i].toCharArray()[0];
}
long[] a = new long[n];
a[0] = num[0];
for(int i = 2; i < n; i+=2){
if(exe[i/2-1]=='*') a[i/2] = a[i/2-1]%MOD*num[i/2]%MOD;
if(exe[i/2-1]=='+') a[i/2] = num[i/2];
a[i/2]%=MOD;
}
long[] b = new long[n];
b[0] = a[0];
int k = 2;
int flag = 1;
for(int i = 2; i < n; i+=2){
if(exe[i/2-1]=='*'){
if(flag == 1) b[i/2] += a[i/2]%MOD;
else b[i/2] += a[i/2] + b[i/2-k]%MOD;
k++;
}
if(exe[i/2-1]=='+'){
flag = 2;
k = 1;
b[i/2] += a[i/2]%MOD + b[i/2-k]%MOD;
k = 2;
}
b[i/2]%=MOD;
}
// for(int i = 0; i < n; i+=2){
// out.println(b[i/2]);
// }
int q = ni();
for(int z = 0; z < q; z++){
s = ns().split(" ");
char c = s[0].toCharArray()[0];
int x = Integer.parseInt(s[1]);
int y = Integer.parseInt(s[2]);
long ans = 0;
int st = x/2;
int go = y/2;
if(c=='?'){
if(st==0){
ans = b[go];
}
else if(exe[st-1]=='+'){
ans = b[go]-b[st-1];
}
else{
long f1 = a[st-1];
for(; st < n/2; st++){
if(exe[st]=='+') break;
}
long f2 = a[st];
ans = f2/f1 + b[go]%MOD - b[st]%MOD;
}
out.println(ans%MOD);
}
if(c=='!'){
if(x%2==1){
int tmp = num[st];
num[st] = num[go];
num[go] = tmp;
}
else{
char tmp = exe[st-1];
exe[st-1] = exe[go-1];
exe[go-1] = tmp;
}
// for(int i = 0; i < n; i++){
// if(i%2==0) out.print(num[i/2]);
// else out.print(exe[i/2]);
// }
Arrays.fill(a,0);
a[0] = num[0];
for(int i = 2; i < n; i+=2){
if(exe[i/2-1]=='*') a[i/2] = a[i/2-1]%MOD*num[i/2]%MOD;
if(exe[i/2-1]=='+') a[i/2] = num[i/2];
a[i/2]%=MOD;
}
Arrays.fill(b,0);
b[0] = a[0];
k = 2;
flag = 1;
for(int i = 2; i < n; i+=2){
if(exe[i/2-1]=='*'){
if(flag == 1) b[i/2] += a[i/2]%MOD;
else b[i/2] += a[i/2] + b[i/2-k]%MOD;
k++;
}
if(exe[i/2-1]=='+'){
flag = 2;
k = 1;
b[i/2] += a[i/2]%MOD + b[i/2-k]%MOD;
k = 2;
}
b[i/2]%=MOD;
}
}
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Main().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b) && b != ' ')){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}