CSES - Datatähti 2022 alku - Results
Submission details
Task:Spiraali
Sender:Nikedi
Submission time:2021-10-09 15:19:25 +0300
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED15
#2ACCEPTED20
#3ACCEPTED65
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.01 s2details
#3ACCEPTED0.01 s3details

Code

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

#include <chrono>
using namespace std::chrono;


int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    long long n;
    long long t;
    long long x;
    long long y;
    cin >> n >> t;
    
    vector<int> tests;
    for(long long i=0;i<t;i++){
        cin >> y >> x;
        tests.push_back(x);
        tests.push_back(y);
    }
    auto start = high_resolution_clock::now();
    
    long long sum=0;
    long long m;

    for(long long u=0;u<2*t;u++){
        x = tests[u];
        u++;
        y = tests[u];
        if(y>=x){//vasen ala 1/2
            if(x+y<=n){//vasen 1/4
                if(x==1){
                    cout << y << "\n";
                }else{
                    /*for(long long k=1;k<=2*x-2;k++){
                        sum += 2*(n-k);
                    }*/
                    m = 2*x-2;
                    sum = 2*m*n-m*(m+1);
                    //cout << "_";
                    cout << n+sum-(n-y)+(x-1) << "\n";
                    sum=0;
                }
            }else{//ala 1/4
                if(y==n){
                    cout << n+x-1 << "\n";
                }else{
                    /*for(long long k=1;k<=2*(n-y);k++){
                        sum += 2*(n-k);
                    }*/
                    m=2*(n-y);
                    sum = 2*m*n-m*(m+1);
                    //cout << "#";
                    cout << n+sum-(n-y)+(x-1) << "\n";
                    sum=0;
                }
            }
        }else{//oike ylä 1/2
            if(x+y<=n){//ylä 1/4
                /*for(long long k=1;k<=2*y-1;k++){
                        sum += 2*(n-k);
                }*/
                m=2*y-1;
                sum = 2*m*n-m*(m+1);
                //cout << "*";
                cout << n+sum+(n-x)-(y-1) << "\n";
                sum=0;
            }else{//oikea 1/4
                /*for(long long k=1;k<=2*(n-x)+1;k++){
                    sum += 2*(n-k);
                }*/
                m=2*(n-x)+1;
                sum = 2*m*n-m*(m+1);
                //cout << ".";
                cout << n+sum+(n-x+1)-y << "\n";
                sum=0;
            }
        }
    }

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    //cout << "Took:" << duration.count() << "microsecond"<< endl;
}

/*
jos y>=x niin vihreä:
    jos x+y<=10 niin vasen 1/4:
        jos x=1:
            cout << y;
        muuten:
            n+sum(2(n-i);1;2*x-2)-(n-y)+(x-1)
    muuten, eli ala 1/4:
        jos y=n:
            cout << n+x-1;
        muuten:
            n+sum(2(n-i);1;2*(n-y))-(n-y)+(x-1)
jos y<x niin punainen:
    jos x+y<10 niin ruskea:
        n+sum(2(n-i);1;2*y-1)+(n-x)-(y-1)
    muuten, eli oike 1/4:
        n+sum(2(n-i);1;2(n-x)+1)+(n-x+1)-y

2mn-n(n+1)



r = 4*rivi

Rivi 1: 1,r(n-1),r(n-1)-1,...,rn-n-2
Rivi 2: ?,?,r(n-2),r(n-2)-1,...,r(n-2)-,?


Vika rivi:  n,n+1,...n,2n-1


n+2(n-1)+2(n-2)+...+2

3 loop

f(x,y)=

n+sum(2(n-i);1;3)

^tossa poikkoilee silleen 
6    16    24    30    34    36
1,6  6,1   2,5   5,2   3,4   4,3
*          *           *
0    1     2     3     4     5

eli diagonaalisesti vasen ala oikee ylä
kun max on parillinen niin vasen ala kun pariton niin oikea ylä

n+sum(2(n-i);1;x)

vihreä vasen ala 1/2
punainen oikea ylä 1/2
ruskea ylä 1/4



*/

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 100
1 1
1 2
1 3
1 4
...

correct output
1
36
35
34
33
...

user output
1
36
35
34
33
...

Test 2

Group: 2

Verdict: ACCEPTED

input
1000 1000
371 263
915 322
946 880
53 738
...

correct output
773533
312166
206053
200080
593922
...

user output
773533
312166
206053
200080
593922
...

Test 3

Group: 3

Verdict: ACCEPTED

input
1000000000 1000
177757853 827347032
409613589 419171337
739269360 256524697
328695530 896842209
...

correct output
571375684522141210
967321186816598569
762879105851175000
370065046779516790
936897883750373771
...

user output
571375684522141210
967321186816598569
762879105851175000
370065046779516790
936897883750373771
...